Quicksort on doubly linked list

Quicksort on doubly linked list

To understand quick sort algorithm, please refer to this post : Quicksort algorithm in C, where we discussed how quicksort is applied to arrays to sort elements. In this post, let’s discuss how to apply quicksort on doubly linked list.

To understand quick sort on doubly linked list, first see what are the basics steps in quick sort :

1. Start with entire set of input.
2. Partition input set at a pivot in such a way elements on left of pivot are smaller and on right are greater than pivot.
3. Now independently sort two partitions got in step 2.

There are separate methods to partition input set into two parts in such a way that pivot is at its right place. One of the methods is given below:

1. set pivot  =  a[high]
2. set i = low - 1
3. for j = l; j <= h-1; j++
   3.a check if a[j] <= pivot
       If yes, increment i; i++;
4. once for loop breaks, swap(a[i+1], a[high])
5. return i+1, which is partition point.

Let’s understand above method on input set : 5,4,2,7,9,1,6,10,8

We call above algorithm with high as low = 0 and high = 8. Pivot = 8 and i=-1. Now loop runs j = 0 to 9.

j = 0 :  a[j] = 5 which is less than pivot. increment i++, i =0 swap(a[i], a[j]). Since i and j are same, nothing changes.

j = 1 : a[j] =  4 which is less than pivot, increment i++, i =1 swap(a[i], a[j]). Since i and j are same, nothing changes.

Same for j = 2 and j =3.  At this point i =3.

j = 4 : a[j] = 9 Since, a[j] is greater than pivot nothing changes. i remains 3

j = 5 : a[j] = 1, increment i++, i =4 swap(a[4], a[5]). Array becomes  5,4,2,7,1,9,6,10,8

j = 6 : a[j] = 2, increment i++, i =5 swap(a[5], a[6]). Array becomes  5,4,2,7,1,6,9,10,8

j = 7 : a[j] = 10, which is greater than pivot, nothing happens. At this point loop finishes.

Now we swap the pivot and a[i+1] i.e a[8] and a[5+1]. Hence, array becomes : 5,4,2,7,1,6,8,10,9

And we return 6 as partition point. Look closely that all elements on left are less than 8 and on right are greater than 8.

Once this partition is done, two parts : 5,4,2,7,1,6, and 10,9 are sorted separately using same quick sort algorithm.

Quick sort implementation on array is given below

Now, coming back to our original problem that is applying quick sort algorithm on doubly linked list. Code remains same, only thing is we first need to find the last node of list. Rest all remains same as array based implementation, except from the way element data is access which is obvious. Below is quicksort algorithm implementation using doubly linked lists

Quicksort on doubly linked list

Complexity of quicksort on doubly linked list is O(n log n) which is same as implementation on array.

Please share if something is wrong or missing, or if there is any suggestion on improvement. We would love to hear what you have to say.