Sorting a Linked List with QuickSort – Simple Algorithm

Google Search Results

You arrived here after searching for the following phrases:

quicksort
c
implementation
linked
list

Click a phrase to jump to the first occurrence, or return to the search results.

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…
quicksort

Here is the program to quicksort arrays

d622b40eb4aa8f6c25674c4fb0256275000

d622b40eb4aa8f6c25674c4fb0256275001

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

d622b40eb4aa8f6c25674c4fb0256275002

d622b40eb4aa8f6c25674c4fb0256275003

d622b40eb4aa8f6c25674c4fb0256275004

d622b40eb4aa8f6c25674c4fb0256275005

d622b40eb4aa8f6c25674c4fb0256275006

Download full source code here

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

comments are always welcome...

Share and Enjoy:

Mike says:

May 18, 2007 at 12:44 pm

I would not like to say simple algorithm but it is understandable as it is similar to arrays version, good work.
Vasant Kumar says:

December 20, 2007 at 3:14 pm

good work
Ron says:

December 24, 2007 at 1:50 pm

yes simple to understand, I was able to map this work to array version of it, BTW I can’t see merge sort here
Kamal says:

July 23, 2008 at 7:51 am

Neat implementation. Thanks for your time.
Johnny Cool says:

October 14, 2008 at 12:32 pm

j– runs into an infinite loop in the above class=”searchterm1″>quicksort module.

Try sorting the following data with above code:
301 -> 101 -> 201 -> 102 -> 201 -> 202 -> NULL

FIX:
(1) Add check “(j >= chain_start)” in j– loop
+
(2) Add check “(i <= (chain_end – 1))” in i++ loop
Thread Pool says:

October 26, 2008 at 9:28 pm

I don’t understand this partition code from the QSort() function:

for(;;)
{
//start partitioning the list
for(;a[i]pivot;j- -);
if (i<j)
Swap(&a[i], &a[j]);
else
break;
}

If a[i] == a[j] == pivot then you will exit out of both for loops, swap the same two numbers, and then continue back to the top of the “for(;;)” loop. Thus resulting in an infinite loop.

If anyone is interested in how to add video to their applications, I posted a article on that here:
http://www.thread-pool.com/2008/10/22/gstreamer/
tsomogyi says:

November 19, 2008 at 5:55 pm

Are you sure that this implementation is really efficient for single-linked lists?
The time complexity of class=”searchterm1″>QuickSort if O(N*logN) – in terms of the number of comparisons, so it is supposed that reaching and swapping elements can be done in constant (O(1)) time.
But it tries to find the previous node in every Swap from the beginning of the list (FindPrev), then Swap becomes linear (O(M), where M is the average length of partial lists), so the time complexity of this implementation is around O(M*N*logN) in terms of advancing item pointer, which can be even worst than e.g. Bubble Sort algorithm (O(N*N)). Intensive usage of GetNthNode and FindPrev elsewhere makes it even worst.
So I would not use this implementation unless somebody corrects my above logic.
sathish says:

March 28, 2009 at 9:24 pm

It runs into infinite loop even with the fix mentioned.

Use int data[] = {0,7,2,5,3,3,6,9,4,1,8,3,9,6};
Prague Hotel says:

April 13, 2009 at 10:23 pm

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

Is “GetNthNode(list, list_start)” part of an included library or do you have to write your own? Sorry, I’m a total newbie at this but now that I’ve discovered this site, I’m sure gonna be following it all the time!

http://www.castlesteps.com/apartments.htm
johnnycool says:

April 20, 2009 at 3:36 pm

Sathish and all,

Sorry for the delayed response. I didn’t check this site lately.

You said that
>>It runs into infinite loop even with the fix
>>mentioned.
>>Use int data[] =
>>{0,7,2,5,3,3,6,9,4,1,8,3,9,6};

Kindly note the following points again.
———————————-
#POINT NO.1#
I corrected this code for linked lists having UNIQUE elements only.

I tried to run my code for the following data set:
0,7,2,5,3,6,9,4,1,8 (removing duplicate values)

It works absolutely fine.
Here is the sample output:
0,1,2,3,4,5,6,7,8,9

———————————-
#POINT NO.2#
Let me re-post the code I modified.

**[BEFORE]**
Function: class=”searchterm1″>quicksort
Line #: 22 (approx.)
for(;left->info info; left=left->next,i++);

for(;right->info > pivot->info; right = FindPrev(list,right),j- -);

**[AFTER]**
Replace the code as below:

while ((left->info info) &&
(i next;
i++;
}

while ((right->info > pivot->a) &&
(j >= chain_start))
{
right = FindPrevListData(p_chain, right);
j–;
}

———————————-

Kindly re-test it and let me know again!
I’m watching this page!
johnnycool says:

April 20, 2009 at 3:43 pm

Reposting my code since it got garbled in the above post.

**[AFTER]**
Replace the code as below:

while ((left->info info) && (i next;
i++;
}

while ((right->info > pivot->info) && (j >= list_start))
{
right = FindPrev(list, right);
j–;
}
johnnycool says:

April 20, 2009 at 3:48 pm

My apologies.
There seems to be some problem while posting operator symbols in my text.
I’m adding white space between the code and re-posting again.

while ( ( left – >info info ) & & ( i next ;
i + + ;
}

while ( ( right – > info > pivot – > info) & & ( j > = chain_start ) )
{
right = FindPrev(list , right);
j – - ;
}
johnnycool says:

April 20, 2009 at 3:54 pm

I am posting it in English text since it is getting garbled everytime. Kindly re-interpret by yourself in language syntax.

a.
while info of left is less than info of pivot AND while i is less than or equal to list_end minus one,
set left equal to next of left.
Increment i by one.

b.
while info of right is greater than info of pivot and j is greater than or equal to list_start,
set right equal to return value from function call FindPrev with arguments as list and right.
Decrement j by one.

Phew! That’s all!
starscream says:

May 13, 2009 at 11:19 am

i dont get it why do peolpe still use C/C++
i beleave pascal is as powerfull as c
and delphi is almost as powerfull as c++
but pascal/delphi are easier to learn,their code is better to go through and debug
i dont get it why take a ride on an 80/miles per hour car when you can take a ride on 80/miles per hour luxury car!
angad says:

May 13, 2009 at 5:50 pm

hey for graphics related programs please visit
http://www.code-heaven.blogspot.com
will post sorting and scheduling algorithms later!!
haris sid says:

May 19, 2009 at 10:17 am

@ star scream
correction: delphi IS as powerfull as c++!
and it actually is generally easier to learn and code
but i was taught c++ in my university and have over 10 years of experiance in it i wont bother learning a new language
though if i was given a choice i would have chosen delphi
Alex Trabek says:

May 28, 2009 at 2:20 am

thanks very much, great information. Keep up the great work.
Zapryan says:

June 19, 2009 at 8:42 pm

When u have more than two equal elements this algorythm also runs in infinite loop.
To avoid this, just add in while loops equation.

“johnnycool said:

…

a.
while info of left is less than or EQAUL to info of pivot AND while i is less than or
….

b.
while info of right is greater than or EQUAL to info of pivot and j is greater than or equal to list_start,

….”

Now it works in all cases.

And I want to thank to the fans of Pascal and Deplphi for make me and my friends laughing our heads off.
sawan says:

September 16, 2009 at 2:55 am

@johnnycool

hey can u plz tell me how i need to change code by ur code
i think there is some syntax error plz let me know what i hv to do exectly

while ((left->info info) && (i next;
i++;
}

what is this mean?
i get second while loop but what is this in first one
admin says:

October 2, 2009 at 10:27 pm

Hi Johnnycool, please insert code between < pre >, < /pre > tags, so that your format will be preserved..