A very short introduction to Quick Sort Algorithm

6 min readMar 20, 2021

Quick Sort Algorithm is a Divide and Conquer Algorithm. The basic concept of Quick Sort algorithm is we choose any element x, and we would be arranging the element x to is correct position. Correct position means that the elements left to x should be smaller than x and the elements right of x should be larger than x.

Let’s go through the pseudo code of quick sort function and the partition function.

Pseudo Code of QuickSort() Function

QuickSort(arr[], l, r){
     
    if (l<r){
        
         int pi = partition (arr[], l, r)         QuickSort(arr[], l, pi-1)
         QuickSort(arr[], pi+1, r)    }}

You may also refer this GitHub Link: QuickSort.txt

The QuickSort function takes in three parameters, arr [], l, r, where arr [] is the unsorted array, l is the starting index of the unsorted array and r is the ending index of the unsorted array. Here pi is the partitioning index which is returned from the partition function. Partitioning index is also known as pivot.

So, after choosing the element we sort the array into two sets of arrays. There might be chances that the arrays we got might not have been sorted. So, we again call off the QuickSort function:

· QuickSort (arr [], l, pi -1)

This QuickSort function is being called off from the starting index till the partitioning index — 1, i.e., till before the partitioning index.

· QuickSort (arr [], pi + 1, l)

This QuickSort function is being called off from the partitioning index + 1 till last element.

You might be wondering for why we didn’t consider the partition index itself. The logic of pivot is that we choose the element in such a way that it should be in its correct position and must not change throughout the problem. So here the value pi (partitioning index) is already in its correct position, so it’s not required to include pi in the function.

Solving a Question using QuickSort Algorithm

Let’s dive in through the procedure of applying quicksort algorithm to solve the question of converting the unsorted array {6, 3, 9, 5, 2, 8, 7} to the sorted array {2, 3, 5, 6, 7, 8 ,9}.

We choose the pivot as to be the last element 7. So, I will partition the array around 7. We receive the following two sets of arrays:

The first set of arrays {6, 3, 5, 2} and the second set of arrays {8, 9}.

First Set of Array Partition {6, 3, 5, 2}:

The pivot is 2 and we will partition around 2. We will receive the following sets of arrays.

Here, we receive the first set of arrays which is basically empty and the second set of arrays which is {6, 3, 5}.
So, since the first set, i.e., {}, is empty so we apply the partition function for the second set {6, 3, 5} which is unsorted.
So, applying the partition function on second set, pivot has been set to 5 and now partitioning around 5. We will receive again two sets of arrays:

Here l == r. So, if we compare the condition with the one that is provided in the pseudocode, we see that the condition is l<r for the conditional statement to work. But in our case, we received l == r. So, we conclude here that the condition becomes False.

Now, let’s move to another set of arrays that was partitioned very early, i.e., {8,9}.

2. Second Set of Array Partition:

Here, we choose the pivot as the last element as well as we had set it to choose.

So, in this set of arrays, we choose the pivot to be 9 and now partitioning around 9. We will receive the following two sets of arrays.

So, after combining all the partitioning and procedures, we get the solution to our question, i.e., a sorted array {2, 3, 5, 6, 7, 8 ,9} for the unsorted array {6, 3, 9, 5, 2, 8, 7}.

Pseudo Code of Partition() Function

Now, let’s move to the pseudo code of the partition function. The most important process behind the quick sort algorithm is played by partition ().

Partition(arr[], l, r){     pivot = arr[r];
     i = l - 1;
     for j= l to r-1
         if arr[j] < pivot
             i++;
             swap(i, j)     swap(i+1, r)
     return i+1}

You may also refer this GitHub Link: partition.txt

Partition () function takes in three parameters, arr [], l, r where arr [] is the unsorted array, l is the starting index of the unsorted array and r is the ending index of the unsorted array.

pivot = arr [r] → We have made the last element as pivot.
i = l -1 → We now take a pointer i which should be l-1, i.e., i would be denoting the last number that is less than pivot.
for j = 1 to r -1 → In the for loop, we take another pointer j that would be traversing from l to r-1.

4. We are comparing arr [j] with the pivot. So, if array of j is less than the pivot, we do:

i++, i.e., we increment the i pointer, and
we swap both the elements at i and elements at j.

if arr [j] < pivot {     i++
     swap (i, j)}

Code Implementation using C++

After going through the logic behind the quick sort algorithm, explanation of the pseudocodes of QuickSort and Partition (), let’s dive into the actual code implementation in C++.

#include<stdio.h> 
void swap(int* a, int* b){    
     int t = *a;    
     *a = *b;    
     *b = t;
}   
// Partition
int partition (int arr[], int l, int r){    
     int pivot = arr[r];        
     int i = (l - 1);       
     for (int j = l; j <= r- 1; j++){        
           if (arr[j] <= pivot){            
                i++;                
                swap(&arr[i], &arr[j]);        
           }    
     }    
     swap(&arr[i + 1], &arr[r]);    
     return (i + 1);
}   
// QuickSort
void quickSort(int arr[], int l, int r){    
     if (l < r){        
           int pi = partition(arr, l, r);         
           quickSort(arr, l, pi - 1);        
           quickSort(arr, pi + 1, r);    
      }
}  
void printArray(int arr[], int size){    
      int i;    
      for (i=0; i < size; i++)        
            printf("%d ", arr[i]);    
            printf("\n");
}  
int main(){    
       int arr[] = {6, 3, 9, 5, 2, 8, 7};    
       int n = sizeof(arr)/sizeof(arr[0]);     
       quickSort(arr, 0, n-1);    
       printf("Sorted array: \n");    
       printArray(arr, n);    
       return 0;
}

You may also refer this GitHub Link: sort.cpp

Output of the above code:

Sorted array:
2 3 5 6 7 8 9

Time Complexity

Now, let’s all look at the time complexity.

Best Case Time Complexity:

We achieve the best-case time complexity when the pivot is the median i.e., pivot would be at the center of the array.
As a result, the sub problem would break into two equal parts, and then we will solve the left part and the right part recursively.

=> T(n)     =        T(n/2) + T(n/2)
=> T(n)     =        2T(n/2) + n
=> T(n/2)   =        2T(n/4) + n/2
=> T(n/4)   =        2T(n/8) + n/4
.
.
.
=> T (1)    =        1

After applying the master’s theorem, we will get the best time complexity as:

T(n) = 𝛉 (n log n)

We can also get the same using the normal conventional method, i.e., using levels

=> (n/(2k)) = 1
=> (n)      = 2k
=> (k)      = log nT(n) = n + n + n + … log n terms
T(n) = 𝛉 (n log n)

2. Worst Case Time Complexity:

We choose the last element as the pivot; We traversed the pivot onto O(n). Then we get the sub problem as T(n-1).

=> T(n)     =        T(n-1) + n
=> T(n-1)   =        T(n-2) + n-1
=> T(n-2)   =        T(n-3) + n-2
.
.
.

So, after applying the master’s theorem we would get the worst-case time complexity as:

T(n) = O(n²)

GitHub Link: https://github.com/atindra305/QuickSort

You can also refer my YouTube video, where I have explained the same:

Thank You So Much !