QuickSort Algorithm

In this series of tutorials regarding sorting algorithms this time we will learn about quicksort. Like Merge Sort, Quicksort is also a recursive algorithm where we divide the list continuously to be able to sort it. The time complexity of quicksort is the average case is O(nlogn). Whereas in the worst case it is O(n^2). However, this worst-case running time is almost always avoided by using a randomized version of quicksort. Randomized quicksort gives us O(nlogn) running time with a very high chance. Additionally, quicksort is an in-place sorting algorithm therefore it takes a constant amount of extra memory.

Despite having a worst-case running time of O(n^2), quicksort is pretty fast and efficient in practical scenarios. Quicksort is often the most practical choice for an efficient sorting algorithm. Interestingly the sort function available in most language libraries are implementations of quicksort algorithm.

Understanding QuickSort

To be able to analyze quicksort in a simpler manner let’s see how to sort a list of integers given to us in a form of an array. Suppose we have an array of 7 integers named X with unordered numbers. Our aim is to sort the following list in increasing order of values by using a quicksort algorithm.

Quick Sort picture 1

Partitioning the list

The first step in quicksort is to select one element from the list and set it as a ‘pivot’. We will rearrange the elements in the list in such a manner that elements lesser than the pivot will come towards the left and those greater than the pivot will come towards the right. Suppose we choose the pivot as ‘5’. In this case, there are four elements (1,2,3,4) that are lesser than the pivot and two elements (6,7) that are greater than the pivot. The elements may be placed in their respective positions in any order. Hence the list will be rearranged as follows:

Quick Sort picture 2

This process is called as the ‘partitioning of the list’.

Partition is a process in which we select a pivot and rearrange the list in such a manner that all elements lesser than the pivot are found towards the left and all elements greater than the pivot are found towards the right.

Sorting the left and right segments

Now what we can do is we can first sort the left side of the array from the pivot and then the right side of the array from the pivot. Unlike merge sort, we would not be required to create temporary arrays for each subarray but can work with the same array. However, in this case, we will have to keep track of the first and last index of both parts. Our array X has elements from indices 0 to 6. The left part of the array from the pivot has indices from 0 to 3 and the right part of the array from the pivot has indices from 5 to 6.

Quick Sort pic 3

Once a list is partitioned we have to sort the two parts: list from the left of the pivot and list from the right of the pivot. In order to sort these two sub arrays, we will again partition these lists.

Further Partitioning

From the left subarray let us first choose a pivot. Assuming ‘2’ is the pivot then element 1 will be towards the left and elements 4 and 3 will be towards the right of the pivot.

Quick Sort pic 5

The left segment at this stage consists of only one element i.e. index 0 with value ‘0’. Thus, no further partitioning will be done on this side. For the right segment, we will choose 3 as the pivot. This moves the element ‘4’ to the right to index 3 and ‘3’ moves to index 2 instead.

Quick Sort partitioning the list

The point to note here is that all the rearrangement is happening in the original array X. The rest of the sub arrays that we are showing are simply the different versions of the array X at different stages. When our segment only consists of a single element, we stop the recursion and then at that point the original array is sorted till that index. In our case the segment from index 0 to 3 is now sorted. Now the original array X from index 0 till index 3 will be 1,2,3,4 making it a sorted arrangement.

Quick Sort pic 6

Point to note: The exit condition from recursion will be when we have only one element in a sub list. At that stage, the sub list is already sorted and we do not need to further break it down.

Pseudocode for Quick Sort

Let us construct pseudocode for quick sort algorithm from whatever information we have gathered till now.

QuickSort(X,start_index,end_index)
{ 
  if (start_index >= end_index) return
 p_index = Partition(X, start_index, end_index)
 QuickSort(X, start_index, p_index-1)
 QuickSort(X, p_index+1, end_index)
}

The Quick Sort function will take in three arguments. The first argument will be the original array X, the second argument will be the start index and the third argument will be the end index. As we are not creating temporary arrays and rearranging elements in the same original array that is why we need to pass the start and end indices of the array.

QuickSort(X,start_index,end_index)

Inside the Quick Sort function, we will call the Partition function that will be responsible for the partitioning logic. The Partition function takes in the array, the start index and the end index of the array on which it will work on. This will rearrange the array in such a way that the segment from the start and all the elements left of the pivot will be lesser whereas all the elements right of the pivot will be greater than the pivot. This function will return the partition index that we will name ‘p_index.’ Thus the Partition function will return us the index of the pivot.

p_index = Partition(X, start_index, end_index)

Afterward, we will make two recursive calls: one to sort the left segment and another to sort the right segment. In this recursive logic, we are assuming that the selected pivot will be the last element in the array.

 QuickSort(X, start_index, p_index-1)
 QuickSort(X, p_index+1, end_index)

To make sure that we do not go into recursion forever, we will include an exit condition. If the start of the segment is greater or equal to the end then we will return. Otherwise, we will keep on splitting and rearranging the array.

if (start_index >= end_index) return

In this case, if the segment only consists of a single element we will return.

Demonstrating

Let us demonstrate this pseudocode with the example we were looking at previously. Now first we are calling QuickSort(X,0,6) as our array name is ‘X’, the start index is 0 and the end index is 6. As the start index is less than the end index thus we will not return and continue further. We will obtain the partition index in ‘p_index.’ Now we will go into recursion. The QuickSort() function will call itself. Now the execution of this particular function will be paused because this function made another function call. Now once again the start index(0) is less than the end index(3) so we will partition. The function QuickSort(X,0,3) will first make a call to QuickSort(X,0,2) and likewise, the partitions will be made and elements will get placed in their appropriate indices.

Let’s see what happens when the QuickSort(X,0,7) function calls the QuickSort(X,5,6) function for the segment right of the pivot. Now the pivot chosen will be 6. As 7 is greater than 6 hence it will move towards the right of the pivot and land at index 6. The pivot will move to index 5 instead. As we are only left with a single element hence the recursion will stop and we will enter the exit condition and return.

Quick Sort pic 7

Now the initial right segment is sorted as well from index 5 to index 6. Thus, the overall array X is sorted from index 0 to index 6.

Quick Sort pic 8

Pseudocode for the partitioning logic

Now let us look at the pseudocode for partitioning the lists using the Partition function. Our aim is to select a pivot and rearrange the elements in such a way that elements lesser than the pivot will be placed at the left side of the pivot and those greater than the pivot will be placed at the right side of the pivot.

Partition(X,start_index,end_index)
{
  pivot=X[end_index]
  p_index=start_index
   for(i=start_index to end_index-1)
    {
       if (X[i]<=pivot)
       {
         swap(X[i],X[p_index])
         p_index++
       }
    }
}

The Partition() function takes in three arguments. The first argument is the name of the array. The second argument is the start index and the third argument is the end index of the array/segment to be partitioned. In our partition function we are selecting the pivot as the element found at the end index. Thus pivot will always be X[end_index].

Now if we pass the following array X to this function then selected pivot will be ‘6’ as it is at the last index.

Quick Sort pic 9

Next, we will create a variable ‘p_index’ that will save the value of the partition index. Initially, it will at the start index i.e. index 0.

Quick Sort pic 10

Loop

The next thing is to examine the array from the start index to (end_index-1) in order to rearrange it by placing elements lesser than 6 towards the left of partition index. Therefore, the partition index will change at each step. This will be achieved using a for() loop from i=start_index to (end_index-1). If the element at that particular index is <= 6(pivot) then we will swap that particular element with the element at the partitioned index. Moreover, we will also increment the partition index.

So lets see what happens when we use this partitioning logic. As you can see above the pivot was selected as ‘6’ and index 0 was set as the partition index initially. Now what happens next is all elements lesser than the pivot will be pushed to the left of p_index. In the for loop, first i=0, now as 4 is less than 6 we will swap but both positions are same: X[0] which is 4 with X[p_index] which is 4. So there will be no swap effect.

Quick Sort pic 11

Then, we will increment ‘i’.

Quick Sort pic 12

Now in the for loop i=1, now as 1 is less than 6 we will swap X[i] and X[p_index]. ‘1’ goes to index 0 and ‘4’ goes to index 1. p_index will also get incremented.

Quick Sort pic 13

At any point all elements towards the left of the partitioned index (p_index) will be lesser than the pivot. These elements are shown in green.

Now again i will be incremented and will be ‘2’.

Quick Sort pic 14

Now in the for loop i=2, now as 5 is less than 6 we will swap X[i] and X[p_index]. ‘5’ goes to index 1 and ‘4’ goes to index 2. p_index will also get incremented.

QuickSort Algorithm Code in C++

#include <iostream>
using namespace std;

int Partition(int* X,int start_index,int end_index)
{
  int pivot=X[end_index];
  int p_index=start_index;
  for(int i=start_index;i<end_index;i++){
      if(X[i]<=pivot){
          swap(X[i],X[p_index]);
          p_index++;
      }
  }
  swap(X[p_index],X[end_index]);
  return p_index;
}

void QuickSort(int* X,int start_index,int end_index){
    if(start_index<end_index){
        int p_index=Partition(X,start_index,end_index);
        QuickSort(X,start_index,p_index-1);
        QuickSort(X,p_index+1,end_index);
        
    }
    
}

int main(){
    int X[]={4,1,5,2,7,3,6};
    cout<<"Original Array: ";
    for(int i=0;i<7;i++)
    cout<<X[i]<<" ";
    cout<<endl;
    QuickSort(X,0,6);
    cout<<"Sorted Array: ";
    for(int i=0;i<7;i++)
    cout<<X[i]<<" ";
    
}

Output

Quick Sort output

Leave a Comment