Manually sort a linked list in the C programming language

Question

How to sort linked list by name in function in C?

struct rec{ char name[20]; int nr; struct rec *nextRec; }; typedef struct rec Rec; /* synonym for struct rec */ typedef Rec *RecPtr; /* synonym for pointer */ void SortLinkedList(RecPtr *sPtr, int p_size);/* prototype */ int main() { RecPtr startPtr = NULL; /* filling upp the linked list... size = nr of nodes in list */ SortLinkedList(&startPtr, size); } void SortLinkedList(RecPtr *sPtr, int p_size){ int i, j; RecPtr tempPtr; RecPtr currentPtr; RecPtr nextPtr; currentPtr = *sPtr; nextPtr = currentPtr->nextRec; for( j = 0; j <= p_size; j++) { /* loop for nr of nodes */ for(i = 0; i <= p_size -1 ; i++) { /* loop for one less than nr of nodes */ if(strcmp(currentPtr->name, nextPtr->name) < 0) { /* it less than ...*/ tempPtr = currentPtr;/* ...swap with temp */ currentPtr = nextPtr; /* but this sorting doesn'nt work */ nextPtr = tempPtr; } currentPtr = nextPtr; currentPtr = currentPtr->nextRec; } } } 

Answer 1

The problem is that you are simply manipulating the pointers, not the objects themselves. When you sort the linked list, you need to break the links and redo them.

For example, in your case there are three links, and they should be changed, as indicated in brackets.

prevPtr-> nextRec (This needs to be changed to point to nextPtr instead of currentPtr) currentPtr-> nextRec (This needs to be changed to point to nextPtr-> nextRec instead of nextPtr) nextPtr-> nextRec (This needs to be changed to point to currentPtr)

You definitely need to have prevPtr and track it in your program.

  nextRec nextRec nextRec 

prevPtr --------------> currentPtr -------------------------> nextPtr --- --- ---------------------> (nextPtr-> nextRec)

Need to change to

  nextRec nextRec nextRec 

prevPtr -----------------------> nextPtr ------------------> currentPtr- --- ---------------> (nextPtr-> nextRec)

Answer 2

Your problem is that you only manipulate RecPtr variables that do not have a permanent effect when you need to manipulate the fields of nextRec structures in the list.

Answer 3

Do not answer your question, but a few comments:

• using typedefs that hide the fact that something is a pointer is usually considered bad style
• If you need sorting, then a linked list is not the best structure to use - you might be better off with an array

Answer 4

WARNING Most likely, it will be redundant for what you want to do. But I'm upset, trying to track a subtle, but unpleasant mistake and need to be distracted.

If I can offer some suggestions ...

First of all, IMO is easier to insert items into a list in order than to sort an unordered list; what I would do is create an insertInOrder function that takes away your list title, a new item to add, and a predicate (function pointer) that compares entries and returns a new chapter to the list:

 Rec *insertInOrder(Rec *head, Rec *new, int (*cmp)(Rec *, Rec *)) { if (head == NULL) { return new; } else if (cmp(new, head) < 0) // new is "less than" head { new->nextRec = head; return new; // new becomes the new head of the list } else { Rec *tmp = head; /** * Find the first element in the list that is not "less than" new */ while (tmp->nextRec != NULL && cmp(new, tmp->nextRec) > 0) { tmp = tmp->nextRec; } if (tmp->nextRec == NULL) { // insert new at end of list tmp->nextRec = new; new->nextRec = NULL; } else { // insert new before tmp->nextRec new->nextRec = tmp->nextRec; tmp->nextRec = new; } // keep the current list head return head; } } 

Now you can order the list based on various criteria. The cmp argument points to a function that takes two record pointers and compares them, returning -1 if the first argument is less than the second, 1 if the first argument is greater than the second, and 0 if they compare equal. For example, if you want to sort by name, define a function like

 int compareNames(Rec *e1, Rec *e2) { int r = strcmp(e1->name, e2->name); if (r < 0) return -1; if (r > 0) return 1; return 0; } 

and call insertInOrder as

 head = insertInOrder(head, new, compareNames); 

To sort the list specified by a specific predicate: starting from the head, delete one item at a time from the existing list and add it to the new list using the specified predicate:

 Rec *sortLinkedList(Rec *head, int (*cmp)(Rec *, Rec *)) { Rec *newList = NULL; while (head) { Rec *tmp = head; head = head->nextRec; tmp->nextRec = NULL; newList = insertInOrder(newList, tmp, cmp); } return newList; } ... head = sortLinkedList(head, compareNr); ... head = sortLinkdeList(head, compareNames); ... head = sortLinkedList(head, compareSomethingElse); 

Like Neil, I don't really like typedefs for pointer types; experience has shown me that they cause more problems than they are worth it.

Answer 5

If you are going to change the order of the linked list, then at some point you will have to write nextRec pointers in the list of links. As the only assignments you make are local pointer variables, you are not making any changes to the list.

You do not reset between cycle i and cycle j , so it’s hard to understand how your algorithm ensures that it does not go out of the list, although often it will not go very far.

If the strcmp test strcmp not run for two iterations, it will always leave nextPtr alone and always assigns currentPtr nextPtr->nextRec , so neither nextPtr nor currentPtr will change.

 currentPtr = nextPtr; currentPtr = currentPtr->nextRec; 

Are you sure you want to use i++ in the body of the loop, as well as part of the for loop increment?

What is your sorting algorithm? Note that if you need to swap two positions in a singly linked list, you will need to save the previous nodes for the exchanged elements so that you can adjust the "next" pointer of the previous nodes.

Answer 6

you can sort the linked list with sorting the bubble easily (iterating through it, tracking the i-th element in case of replacement). You can also do quicksort easily (in fact, I heard some people think that quicksort makes more sense in a linked list than in an array).

Answer 7

You can sort the list by sort type or bubble sort. Instead of data, you need to change the pointer. Below I give both examples that may be useful for your problem.

 struct link { int data; struct link *next; }; selection(struct link **first) { struct link *p,*q,*pp,*qq,*temp; pp=p=*first; while(p->next!=NULL) { q=p->next; while(q!=NULL) { if(p->data > q->data) { if(p==*first) { if(q==p->next) { p->next=q->next; q->next=p; } else { temp=q->next; q->next=p->next; p->next=temp; qq->next=p; } *first=q; pp=*first; } else { if(q==p->next) { p->next=q->next; q->next=p; pp->next=q; } else { temp=q->next; q->next=p->next; p->next=temp; qq->next=p; pp->next=q; } } temp=p; p=q; q=temp; } qq=q; q=q->next; } pp=p; p=p->next; } return 0; } bable(struct link **first) { struct link *p,*q,*lt,*pp,*temp; lt=NULL; p=*first; while((*first)->next!=lt) { pp=p=*first; while(p->next!=lt) { q=p->next; if((p->data)>(q->data)) { if(p==*first) { p->next=q->next; q->next=p; *first=q; pp=*first; } else { p->next=q->next; q->next=p; pp->next=q; } temp=p; p=q; q=temp; } pp=p; p=p->next; } lt=p; } return 0; } 

Answer 8

I would suggest merge sort in the list, since it is O (N Log N), while bubble sort or insert sort is O (N ^ 2).

Here's a good example of a simple merge sort with a merged list .