Manually sort a linked list in the C programming language

Question

How do you sort a linked list by name in a 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

Your problem is that your are only manipulating the RecPtr variables, which has no permanent effect, when you should manipulate the nextRec fields of the structs in the list instead.

Answer 2

Not to answer your question, but a couple of observations:

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

Answer 3

If you are going to changed the order of a linked list then at some stage you are going to have to write to the nextRec pointers on the link list. As the only assignments that you make are to local pointer variables you are not making any changes to the list.

You don't do any resetting between the i loop and the j loop so it's hard to see how your algorithm guarantees not to go beyond the end of the list, although often it's not going to move very far.

If the strcmp test doesn't trigger for two iterations then it will always leave nextPtr alone and always assign currentPtr to nextPtr->nextRec so neither nextPtr nor currentPtr will change.

currentPtr = nextPtr;
currentPtr = currentPtr->nextRec;

Do you really mean to use i++ in the loop body as well as the increment part of the for loop?

What is your sorting algorithm? Note that if you need to swap two elements position in a singly linked list then you will need to retain the previous nodes to the elements being swapped so that you can adjust the previous nodes' "next" pointer.

Answer 4

The problem seems to be that you are just manipulating the pointers and not the objects themselves. When you sort a linked list, you necessary have to break links and re-make them.

For example, in your case there are three links and they have to be modified as specified in the 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 necessarily need to have a prevPtr and keep track of it in your program.

        nextRec                   nextRec           nextRec

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

Needs to be changed to

           nextRec           nextRec              nextRec

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

Answer 5

you can sort a linked list with bubble sort easily(iterating through it, keeping track of the i-1th element in case of swapping). You could also do a quicksort rather easily(in fact, I've heard some people suggest that quicksort makes more sense on a linked list than on an array).

Answer 6

You can sort the list either through selection sort or bubble sort. Instead of data you need to swap the pointer. Below I am giving both sort examples which may helpful to your issue.

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 7

WARNING: The following is most likely overkill for what you're wanting to do. But I'm frustrated trying to track down a subtle but nasty bug and need a distraction.

If I may offer some suggestions...

First of all, IMO it's 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 your list head, the new element to be added, and a predicate (a pointer to a function) that compares records, and returns the new head of 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 different 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 names, 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, given a particular predicate: starting at the head, remove one element at a time from the existing list and add it to a new list, using the indicated 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'm not terribly fond of typedefs for pointer types; experience has shown me that they cause more problems than they're worth.

Answer 8

I would suggest merge-sort on the list as it is O(N Log N) while bubble-sort or insertion-sort are both O(N^2).

Here's good example of a simple singly linked list merge sort.