Example and Source Code for Quick Sort

Written by Raza on. Posted in C++

In the previous post I elaborated on Quick Sort and its basic principles, recursive technique, how to select the pivot and the comparison of quick sort and bubble sort. Today I shall explain a sample problem step by step and then write a source code for it. As I mentioned, I would be considering the first element of the list as the pivot. Watch for the next paragraphs for step by step procedure and source code.

 

Example Procedure of Quick Sort:

I shall once again enumerate the three steps in quick sort algorithm.

  1. Choose a pivot from the list.
  2. Move elements smaller than pivot to its left and larger ones to its right. Thus the pivot acts as a boundary between the two portions.
  3. Sort these two portions or partial lists separately by recursion.

 

Consider this list as an example for today’s article.

20, 13, 5, 26, 3, 27, 1, 32

 

Choose the temporary pivot as the first element which is 20. After that, select two indexes L and R. R is at the last index of the list and L is the second index of the list, first after pivot. In this case, 32 is at R and 13 is at L. R would be shown in bold and L would be underlined like this.

20, 13, 5, 26, 3, 27, 1, 32

 

What we are going to do is that we are going to select a suitable pivot from the list and then move smaller elements to its left and greater elements to its right. For this, we shall compare values L and R with the pivot and adjust the positions accordingly. These are the steps in detail.

1. Move index R to the left until it reaches L, or it reaches a value smaller than pivot. In the example, we start moving R from 32. First we reach 1 which is smaller than the pivot so we stop here.

20, 13, 5, 26, 3, 27, 1, 32

 

2. Now move L to the right until it reaches R, or it reaches a value greater than pivot. In the example, we move L from 13 to 5 and then 26. 26 is greater than pivot 20, so we stop here.

20, 13, 5, 26, 3, 27, 1, 32
3. If L and R are not at the same index, swap their values. Here, 26 and 1 would be swapped.

20, 13, 5, 1, 3, 27, 26, 32

4. Repeat the steps 1 to 3. At this time, 26 is at R and 1 is at L. Moving R to the right, until it reaches L or a value smaller than pivot, we rest at 3.

20, 13, 5, 1, 3, 27, 26, 32


5. Move L to the right with same procedure. L was initially at 1 and it reaches 3 which is at R. L and R are at the same position now, so stop comparing anymore in this step.

20, 13, 5, 1, 3, 27, 26, 32


6. Normally at this point when L and R coincide, we would be at the value that would be the smallest from the right side. If we start looking from the right hand side here, all values to the right of 3 are greater than 3. So, the final step is to swap this value with the pivot value which we chose in the beginning. The list is like this now.

 3, 13, 5, 1, 20, 27, 26, 32


7. At this stage, our List has been divided into two portions with the pivot as a boundary in between them. To the right of pivot, larger values are present and to its left smaller values are present. From this function, we return index of the final pivot or the boundary.


8. There is a special case when the pivot value we chose in the beginning happens to be the smallest value of the list. In that particular instance, we return the starting index of the List.

This was the first step or partition in quick sort process. After this step, two smaller lists have been made and we have to sort them individually using the same procedure. So actually there are two functions working here. One function chooses the pivot, creates a partition in the larger list creating two sub lists. The other one calls the partition function on those smaller sub lists.

Remember while writing the source code for quick sort that in recursion, you have to consider the base case specifically. Base case is the condition when recursion process terminates. In quick sort, base case would be the situation when the starting index becomes equal to or greater than the ending index of the list.

 

Source Code for Quick Sort:

A simple source code of Quick sort program with first value chosen as pivot would be like this.

 

</p>
<p>int partition_array(int arr[], int start, int end)<br />
{<br />
.  int pivot = arr[start] ;<br />
.  int L = start + 1 ;<br />
.  int R = end ;<br />
.  int temp = 0 ;</p>
<p>.  while (true)<br />
.  {<br />
.   while ( (L &lt; R) &amp;&amp; (arr[R] &gt;= pivot) )  //bringing R to the left<br />
.    --R ;<br />
.   while ( (L &lt; R) &amp;&amp; (arr[L] &lt; pivot) )  //bringing R to the right<br />
.    ++L ;<br />
.<br />
.   if (L == R) //If they coincide<br />
.    break ;</p>
<p>.//swapping L and R<br />
.   temp = arr[L] ;<br />
.   arr[L] = arr[R] ;<br />
.   arr[R] = temp ;<br />
.  }</p>
<p>.<br />
.  if (pivot &lt;= arr[L])  //special case<br />
.   return start ;</p>
<p>.<br />
.  arr[start] = arr[L] ;  //real pivot<br />
.  arr[L] = pivot ;<br />
.  return L ;<br />
}</p>
<p>.</p>
<p>void quick_sort(int arr[], int start, int end)<br />
{<br />
.  if (start &lt; end)<br />
.  {<br />
.   int boundary = partition_array(arr, start, end) ;<br />
.   quick_sort(arr, start, boundary - 1) ;<br />
.   quick_sort(arr, boundary + 1, end) ;<br />
.  }</p>
<p>}<br />
.<br />
int main ()<br />
{<br />
.  const int SIZE = 10 ;<br />
.  int arr[SIZE] = {11, 31, 7, 8, 1, 110, 4, 87, 10, 6} ;<br />
.  quick_sort(arr, 0, SIZE - 1) ;<br />
.  for (int i = 0 ; i &lt; SIZE ; ++i)<br />
.   cout &lt;&lt; arr[i] &lt;&lt; " " ;<br />
}</p>
<p>

 

So this was the fastest algorithm in computer science. Some other very good sorting algorithms are in practice as well though none is as good as quick sort. The direct competitors are merge sort and heap sort which we might cover later in our posts. There are many variant of quick sort as well. You can try them out on your own. If you come up with a good one, don’t hesitate to share with us!

Tags: , , , ,