Quicksorting linked list - simple algorithm

[openuser]

I came across a simple way of quicksorting linked list which is same as iterative version of quicksort for arrays...
http://www.openasthra.com/c-tidbits/sorting-a-linked-list-with-quicksort-simple-algorithm/
worth a look...

Let me know if you have any other simple algorithm for QuickSort (for sorting linked lists), should be easy to understand...

Thanks.

[iMalc]

I came across a simple way of quicksorting linked list which is same as iterative version of quicksort for arrays...
http://www.openasthra.com/c-tidbits/sorting-a-linked-list-with-quicksort-simple-algorithm/
worth a look...

Let me know if you have any other simple algorithm for QuickSort (for sorting linked lists), should be easy to understand...

Thanks.

I had a look at that link and I'm afraid to tell you that it is of very poor quality. The spelling is horrible, and in fact it does NOT really implement list-based-quicksort.

What it actually does is implement array-based-quicksort, and treats a linked-list as an array. This leads to extremely poor performance. In fact I think that the implementation on that site is about O(n^3) or N-cubed. Not to mention it is far longer than it should be for this algorithm.

Perhaps you would consider taking a look at a page from my own personal site which I am currently putting together, instead: <URL snipped>

My explanations are currently a bit too brief, I'm constantly working on it and uploading a new copy every few days. Feel free to ask me questions about it.

Also, if you don't necessarily have to use quicksort, then you may consider looking around at some of the alternatives on that page. Again, please feel free to ask for me to provide more explanations where they would help.

[openuser]

I had a look at that link and I'm afraid to tell you that it is of very poor quality. The spelling is horrible, and in fact it does NOT really implement list-based-quicksort.

I can clearly see it is manipulating linked list links

In fact I think that the implementation on that site is about O(n^3) or N-cubed. Not to mention it is far longer than it should be for this algorithm.

where is the O(n^3) coming out there in the algo, I'm not convinced.

Perhaps you would consider taking a look at a page from my own personal site which I am currently putting together, instead: <URL snipped>

I would like to see your algo but, URL was snipped, I do not know the reason.

[Ancient Dragon]

I downloaded the source and tried to compile as a C program using Visual C++ 2005 Express. Lots of compile errors, probably all of them are solvable if you are alreay comfortable with C language. Don't expect to use that code as-is -- you will have to make code changes and add at least one undefined function.

[Ancient Dragon]

The more I look at this code the less I like it -- even after fixing all compile errors the code does not work. The linked list before and after sorting are identical. The author obviously failed to compile and test this program before posting it, and he should be ashamed of himself for doing that. You would be better off not using that program.

[iMalc]

I can clearly see it is manipulating linked list links

where is the O(n^3) coming out there in the algo, I'm not convinced.

I would like to see your algo but, URL was snipped, I do not know the reason.

Yes it is manipulating a linked list, but it is clearly only a leaky-abstraction placed on top of an array implementation. (Leaky in that random access isn't O(1))

The O(n^3) comes from the fact that quicksort is O(n^2) when swapping nodes is O(1), but you can clearly see that SwapNodes calls FindPrev which is O(n), and O(n) * O(n^2) = O(n^3). QED.

I must appologise for posting the link to my own site, even thought I created it specifically for helping others, I may not do so. I'm sure that the Admin would not realy have thought it was spam, but I respect that they have rules to uphold and can't afford to make execptions.
You should be able to find it from the link in my sig (if that is working).

[Ancient Dragon]

Just in case anyone is interested here is the corrected sorting algorithm in the link in the original post. It had several bugs that I fixed and sent to the admins of that site too. It sorts an linked list of integers. If you want it to sort something else, such as floats or structures you will have to make appropriate changes to the quicksort() function.

I'm not vouching for its efficiency -- there may be more efficient ways of doing it. Only saying here that it works.

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

typedef struct Node Node;


struct Node
{
  void* info; //data
  Node* next; //used to point to next node
};


//this implementation doesn't use any explicit special header node
//one has to maintain a start point of a list to track all other nodes
//so createlist is a dummy one
Node *createlist()
{
  return NULL;
}

//insert after a known node and return the node before inserted node
Node *insert(Node *after, long* data)
{
  Node* n;
  n = malloc (sizeof(Node));
  n->info = data;

  //incase header node is not created
  if (!after)
  {
    n->next = after;
    return n;
  }

  n->next = after->next;
  after->next = n;

  return after;
}

void destroylist(Node **n)
{
  Node * tmp;

  if (!n || !*n)
  {
    return;
  }

  while(*n)
  {
    tmp = (*n)->next;  
    free(*n);
    *n = tmp;
  }
}


//given a node in list, prints entire list after the node
int printlist(Node *h)
{
  Node* t = h;

  while(t)
  {
    printf(" %d ->", *(long*)t->info);
    t = t->next;
  }

  printf(" NULL\n");
  return 0;
}


//find previous node of curr node
Node *FindPrev(Node *list, Node *curr)
{
  for(;list && list->next; list=list->next)
  {
    if(curr == list->next)
    {
      break;
    }
  }

  if (list->next != curr)
  {
    //not find any element, probably what we are 
    //searching for is the beginning node
    return curr;
  }

  return list;
}

/*A complete swap algorithm which cares of 
several scenarios while swapping two nodes in 
a linked list which doesn't have any special nodes
scenarios considered while swapping
1)two nodes which are far away
2)two nodes which are far away, one is node is at 
  beginning of the list
3)two node which are neighbors
4)two nodes which are neibhors, 
  one node is at beginning of the list
*/
Node *SwapNodes(Node *list, Node *node1, Node *node2)
{

  Node *node1prev, *node2prev, *tmp;

  node1prev = FindPrev(list, node1);
  node2prev = FindPrev(list, node2);

  tmp = node2->next;

  //check whether node to swapped is in 
  //beggining (i.e. header node)
  if (node1 != list)
  {
    node1prev->next = node2;
  }
  else
  {
    //as we do not have special header node, 
    //if the first node and some 
    //other node, need to be swapped, 
    //then update the list (makes new min node as 
    //logical header)
    list = node2;
  }

  //are nodes to be swapped neibgoring nodes?
  if (node1->next == node2)
  {
    //nodes to be swapped are neibhoring nodes,
    //then swap them simply
    node2->next = node1;
    node1->next = tmp;
  }
  else
  {
    //nodes to be swapped are not neibhor nodes, 
    //they are apart
    //so, consider all scenarios
    node2->next = node1->next;

    node1->next = tmp;
    node2prev->next = node1;
  }
  return list;
}

/*an auxilory routine for getting the Nth 
element in the linked list*/
Node *GetNthNode(Node *list, int n)
{
  int i=1;
  for(i=1;i<n;i++)
  {
    list = list->next;
  }
  return list;
}

/*count number of nodes between two nodes 
(including the start, end mentioned)*/
int NumNodes(Node *list, Node *end)
{
  int i;

  for(i=1;list && (list!=end);i++)
  {
    list = list->next;
  }

  if (list != end)
  {
    return 0;
  }
  return i;
}

//total nodes in list
int countnodes(Node *list)
{
  int i = 0;

  for (;list; list=list->next)
  {
    i++;
  }

  return i;
}

/*select a pivot, pivot can be selected in any way
randomly, first element, median of left, center, right
elemnts, etc.
Here we have chosen to pick center element as pivot*/
Node *SelectPivot(Node *list, Node *end)
{
  Node *right, *noden;
  int n;

  n=NumNodes(list, end);

  noden = GetNthNode(list, (int)((float)n/2+0.5));
  //
  right = FindPrev(list, end);

  if (noden != right)
  {
    //swap the pivot and right most element in the list
    //later pivot will be restored.
    SwapNodes(list, noden, right->next);
    return noden;
  }
  else
  {
    return noden->next;
  }
}

/*the actual quciksort routine*/
Node * quicksort(Node *list, int list_start, int list_end) 
{
  Node *pivot, *left=list, *right=list, *tmp;
  int i = list_start, j= list_end-1;

  if (list_start >= list_end)
  {
    return list;
  }

  right = GetNthNode(list, list_end);
  left = GetNthNode(list, list_start);

  //select pivot
  pivot = SelectPivot(left, right);

  right = FindPrev(left, pivot);

  for(;;)
  {
    //now starts partitioning the list
    for(;*(long*)left->info < *(long*)pivot->info; left=left->next,i++);

    for(;*(long*)right->info > *(long*)pivot->info; right = FindPrev(list,right),j--);
    if (i < j)
    {
      list = SwapNodes(list, left, right);
      tmp = left;
      left = right;
      right = tmp;
    }
    else
      break;
  }

  //restore pivot
  list = SwapNodes(list, left, pivot); 

  //now sort on smaller linked lists
  list = quicksort(list, list_start, i-1);
  list = quicksort(list, i+1, list_end);

  return list;
}

//a wrapper for quicksort
Node *QSort(Node *list)
{
  int n;
  
  n=countnodes(list);

  //call the quick sort routine
  //we always number elements in linked list as
  //1,2..n instead of 0, 1.. n-1
  return quicksort(list, 1, n);
}

#define TEST
#ifdef TEST

int main()
{
  int i;
  Node *list2 = NULL;
  long data[] = {8,0,7,2,5,3,6,9,4,1};  
  //list2
  for(i = 0; i < sizeof(data)/sizeof(data[0]); i++)
    list2 = insert(list2, &data[i]);

  printf("unsorted linked list:\n");
  printlist(list2);

  printf("sorted linked list:\n");
  list2 = QSort(list2);
  printlist(list2);

  destroylist(&list2);
}

#endif