Descending Sort function for linked list in C?

Question

So I have a linked list that contains two elements, a 3 character string that is read in, and an integer value. I need to sort the strings by their respective int values in a descending fashion. I'll link the whole block of code and then point out exactly where I'm getting stuck.

The code runs fine until it hits the sort() function. Then it gets caught in some infinite loop. The program is supposed to end when the user input string is 'end'.

void sort() {
    struct node *ptr1, *ptr2;
    ptr1 = ptr2 = head;
    while(ptr1 != NULL){
        ptr2 = ptr1;
        while(ptr2 != NULL) {
            if(ptr1->val < ptr2->val){
                ptr2 = ptr2->next;
            }
        }
    }
}


int main(void) {
    char str[CMDSIZE];
    head = NULL;
    struct node *temp;
    int randomnumber;
    randomnumber = (rand() % 10) + 1;


    while(strcmp(str, "end") != 0) {
        printf("Enter your command: ");
        fflush(stdout);
        scanf("%[^\n]%*c", str);
        insert(str, randomnumber);
        randomnumber = (rand() % 10) + 1;
    }
    sort();
    print();

}

Full code below:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define CMDSIZE 4

struct node
{
    char cmd[4];
    int val;
    struct node *next;
};

struct node *head = NULL;
struct node *curr = NULL;


void insert(char command[], int x) {
    struct node *temp;
    temp = (struct node*)malloc(sizeof(struct node));
    strcpy(temp->cmd, command);
    temp->val = x;
    temp->next = head;
    head = temp;
}

void print() {
    struct node *temp;
    temp = head;
    printf("\n Linked List Contents : \n");
    while(temp!=NULL){
        printf(" Node contains :\n %s %d \n", temp->cmd, temp->val);
        temp=temp->next;
    }
}

void sort() {
    struct node *ptr1, *ptr2;
    ptr1 = ptr2 = head;
    while(ptr1 != NULL){
        ptr2 = ptr1;
        while(ptr2 != NULL) {
            if(ptr1->val < ptr2->val){
                ptr2 = ptr2->next;
            }
        }
    }
}


int main(void) {
    char str[CMDSIZE];
    head = NULL;
    struct node *temp;
    int randomnumber;
    randomnumber = (rand() % 10) + 1;


    while(strcmp(str, "end") != 0) {
        printf("Enter your command: ");
        fflush(stdout);
        scanf("%[^\n]%*c", str);
        insert(str, randomnumber);
        randomnumber = (rand() % 10) + 1;

    }
    sort();
    print();

}

I use random 3 character strings for the input until I type 'end' and the sort function runs.

Output with sort():

Enter your command: lll
Enter your command: ooo
Enter your command: man
Enter your command: bmi
Enter your command: end

Output without sort():

 Linked List Contents : 
 Node contains :
 end 9 
 Node contains :
 two 4 
 Node contains :
 one 10 
 Node contains :
 lll 8

Is this an assignment, or some other learning project, or could you consider using `qsort(...)`? — ryyker, Mar 22 '17 at 18:17
_...it hits the sort() function. Then it gets caught in some infinite loop..._. It appears both answers offer an explanation. Have you tried to use the information from either? — ryyker, Mar 22 '17 at 18:19
http://stackoverflow.com/questions/7685/merge-sort-a-linked-list — sp2danny, Mar 23 '17 at 08:11

score 0 · Answer 1 · answered Mar 22 '17 at 17:25

0

In this loop

while(ptr2 != NULL) {
   if(ptr1->val < ptr2->val){
       ptr2 = ptr2->next;
   }
}

If ptr2->val >= ptr1->val ptr2 will not be changed for the next iteration of the loop which means that the loop never terminates.

answered Mar 22 '17 at 17:25

JeremyP

84,577
15
123
161

score 0 · Answer 2 · answered Mar 22 '17 at 17:32

It looks like your sort routine isn't any where near finished.

Both of the loops have the possibility to run for ever. For the outer one, you never change the value of ptr1 so it'll never end - the inner one only changes ptr2 under some circumstances.

Ultimately, nothing inside the function actually changes the order of the list so I'm not sure why you think it's ready to be used.

score 0 · Answer 3 · answered Mar 23 '17 at 01:35

A simple way to do the sort is to remove nodes from the original list and insert them into order into an initially empty list. Since this is probably homework, I can't provide a complete answer, so here is the basic idea:

struct node *sorted = NULL;    // initially empty list
// ... remove nodes from head, insert nodes in order into sorted

Descending Sort function for linked list in C?

3 Answers3