Related Blog Items

• Sorting A Linked List with Bubble Sort
• Sorting a Linked List with Selection Sort
• Swapping nodes in a single linked list
• Reversing a circular single linked list using pointers
• Sorting a Linked List

Quicksort is the fastest known sorting algorithm in practice. Its average running time is O(nlogn). It is based on devide and conquer idea:
partition into two lists and put them back together again. It does more work on the divide side, less on the combine side.

The basic algorithm is
1)pick any element (called as Pivot) in list
2)Partition the list as two parts, first part contains all the elements which are less than pivot, the other contain all the elements which are greater than pivot
3)do quicksort recursively on sub lists

Regarding step1:
Any element can be selected as pivot, but some choices may cause bad performance. Example. first element everytime: this pivot cause bad performance on presorted or lists in reverse sorted order, because all elements go into one sublist. One safe strategy is choosing pivot randomly.

regarding Step2:
As already pointed out quicksort does most of the work while partitioning the lists, so this is the step which is a bit complex..

both step1 and 2 are represented graphically below…

Here is the program to quicksort arrays

void Swap(int *a, int *b)
{
  int tmp;
  tmp = *b;
  *b=*a;
  *a=tmp;
}
 
int SelectPivot(int a[], int left, int right)
{
  int center = (left+right)/2;
  Swap(&a[center], &a[right]);
  return a[right];
}

 
void QSort(int a[], int left, int right)
{
  int i,j;
  int pivot;
 
  if (left >= right)
  {
    return;
  }
 
  pivot = SelectPivot(a, left, right);
  i = left;
  j = right-1;
 
  for(;;)
  {
    //start partitioning the list
    for(;a[i]<pivot;i++);
    for(;a[j]>pivot;j- -);
    if (i<j)
      Swap(&a[i], &a[j]);
    else
      break;
  }
 
  //restore pivot
  Swap(&a[i], &a[right]);
 
  QSort(a, left, i-1);
  QSort(a, i+1, right);
 
  return;
}
 
//usage
int main()
{
  int a[10] = {1,9,10,8,2,7,3,6,4,5};
  QSort(a,0,9);
  return 0;
}

Finally, here is the program for sorting linked list using quicksort, it very simple and esay to understand, if you understand
quicksorting arrays well, then this algo can be easyly interpreted on same lines.

Sorting Linked List using QuickSort

/*the actual quciksort routine for sorting linked list*/
/*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(;left->info < pivot->info; left=left->next,i++);

    for(;right->info > pivot->info; right = FindPrev(list,right),j- -);
    if (i < j)
    {
      list = SwapNodes(list, left, right);
      //left, right ptrs got swapped, to continue
      //traversing we need them back at same positions
      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;
}

All auxiliary functions

//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 auxiliary 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;
}

 
/*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, (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;
  }
}
 
int countnodes(Node *list)
{
  int i = 0;
 
  for (;list; list=list->next)
  {
    i++;
  }
 
  return i;
}

//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);
}
 
int main()
{
  Node *list2;
  //list2
  list2 = insert(list2, 8);
  insert(list2, 0);
  insert(list2, 7);
  insert(list2, 2);
  insert(list2, 5);
  insert(list2, 3);
  insert(list2, 6);
  insert(list2, 9);
  insert(list2, 4);
  insert(list2, 1);
  printf("unsorted linked list:\n");
  printlist(list2);
 
  printf("sorted linked list:\n");
  list2 = QSort(list2);
  printlist(list2);
  return 0;
}

Download full source code here

If you are interested in more operations on linked list, visit this post

comments are always welcome…

Post any questions for more understanding over here…

Popularity: 97%

You need to log on to convert this article into PDF

Related Blog Items

• Sorting A Linked List with Bubble Sort
• Sorting a Linked List with Selection Sort
• Swapping nodes in a single linked list
• Reversing a circular single linked list using pointers
• Sorting a Linked List

This entry was written by ponnada and posted on May 1, 2007 at 7:42 pm and filed under C Tidbits, Data Structures in C/C++. Bookmark the permalink. Follow any comments here with the RSS feed for this post. Post a comment or leave a trackback: Trackback URL.