Quick Sort Explained | C++ STL

Partition Algorithm and Time Complexity

Published in

ALgo 101

4 min readJan 8, 2022

As the name suggests Quick Sort — is an Arrangement technique that can sequence the array of lower value to highest value or vice versa.

It is based upon the Divide and Conquer Technique and has a Time complexity of O (nlogn).

The primary nuts and screws of this sort can be framed as:

Pick an element as pivot and partition the given array around the picked pivot.

There are many different versions of quickSort that pick pivot in different ways.

Always pick the first element as a pivot.
Always pick the last element as a pivot. {Used Here}
Pick a random element as a pivot.
Pick median as a pivot.

In this explanation, we will be focusing just on picking the last element as a pivot to keep it clearer.

Simple Steps to Quick Sort.

The entire Quick Sort can be broken down into two steps:

Partition the array.
Divide the array around the pivot.

The key process of Sorting down the Array is to find the sorted place of the pivot.

Pivot Partition()

The most common way of finding partition is to start from the leftmost element and find elements that are smaller than the pivot and only then increment a dummy index i. Once we find the element that is a smaller element we swap out the current element with ith element and repeat the process.

Example courtesy of GeeksforGeeks:

arr[] = {10, 80, 30, 90, 40, 50, 70}
Indexes:  0   1   2   3   4   5   6 

low = 0, high =  6, pivot = arr[h] = 70
Initialize index of smaller element, i = -1

Traverse elements from j = low to high-1
j = 0 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 0 
arr[] = {10, 80, 30, 90, 40, 50, 70} // No change as i and j 
                                     // are same

j = 1 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 2 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 1
arr[] = {10, 30, 80, 90, 40, 50, 70} // We swap 80 and 30 

j = 3 : Since arr[j] > pivot, do nothing
// No change in i and arr[]

j = 4 : Since arr[j] <= pivot, do i++ and swap(arr[i], arr[j])
i = 2
arr[] = {10, 30, 40, 90, 80, 50, 70} // 80 and 40 Swapped
j = 5 : Since arr[j] <= pivot, do i++ and swap arr[i] with arr[j] 
i = 3 
arr[] = {10, 30, 40, 50, 80, 90, 70} // 90 and 50 Swapped 

We come out of loop because j is now equal to high-1.
Finally we place pivot at correct position by swapping
arr[i+1] and arr[high] (or pivot) 
arr[] = {10, 30, 40, 50, 70, 90, 80} // 80 and 70 Swapped 

Now 70 is at its correct place. All elements smaller than
70 are before it and all elements greater than 70 are after
it.

Building the Divide and Conquer recursion.

This will be a basic recursion implementation, with the partition being made around the pivot.

Recursion Pseudo code:

/* low  --> Starting index,  high  --> Ending index */
quickSort(arr[], low, high)
{
    if (low < high)
    {
        /* pi is partitioning index, arr[pi] is now
           at right place */
        pi = partition(arr, low, high);        quickSort(arr, low, pi - 1);  // Before pi
        quickSort(arr, pi + 1, high); // After pi
    }
}

Final Code.

C++ Code

Always picking the last element as pivot.

View the Code Here:

class Solution {
public:     //Partiton implementation
    int partition(vector<int>& nums,int low, int high)
    {
        int i=low-1;
        //choosing pivot as last element 
        int pivot=nums[high];
        for(int j=low;j<high;j++)
        {
            if(nums[j]<=pivot)
            {
                i++;
                swap(nums[i],nums[j]);
            }
        }
        swap(nums[i+1],nums[high]);
        return i+1;
    }
    // DNC implementation
    void quicksort(vector<int>& nums,int low, int high)
    {
        if(low<high)
        {
            int pivot=partition(nums,low,high);
            quicksort(nums,low,pivot-1);
            quicksort(nums,pivot+1,high);
            
        }
    }
    //
    vector<int> sortArray(vector<int>& nums) {
         quicksort(nums,0,nums.size()-1);
         return nums;
    }
};

Time Complexity:

Best case scenario: The best-case scenario occurs when the first pivot element will divide the entire Array into two equal halves and the subsequent pivot also do the same.
The calls will be we taking cn, cn/2, cn/4, and so on.
The best-case complexity of the quick sort algorithm is O(n logn)

Example of a Best Case Scenario:

[10,20,50,40,30]

[10,20] [30] [50,40]……. continues

Worst case scenario: The worst case that can happen is when we have a completely opposite sorted Array or reverse order. The original call takes n iterations, subsequent one will take n-1, n-2 .. and so on.

Example:

[50,40,30,20,10]

[10] [50,40,30,20] …….. continues

The worst-case time complexity of Quick Sort would be O(n2).