Quick Sort Algorithm

Step1: Where is the quick sort from?

In a out-of-order array, if we fixed one of them and name it “pivot”, such as the middle one or the first one, and next we divided the array into two parts(left and right). We put the one bigger than privot in the left part, put the one smaller than pivot in the right part. Repeat the process, we can finally get the sorted array.

Step2: What can we achieve it with c++?

• First, we need the “pivot”. Generally speaking, we often define the first one or the middle one of the array as pivot. And we should divide the array into two parts. That means that we need two pointers, which point the last first one and the last one.

(Attention, there are some difference of setting pointers between defining the first one and the middle one of the array as pivot)

For the first one:

int i = l; int j = h; 
 /* 
That because we should keep the l and h unchanged.
The 'l' point the first index of the element of the array. 
The 'h' point the index after the last element of the array.
*/
int pivot = arr[i];

For the middle one:

int i = l; int j = h;
int middle = i + (j - i) / 2; // Avoid Overflow
int pivot = arr[middle];
/*
The 'l' point the index before the first element of the array. 
The 'h' point the index after the last element of the array.
*/

• Second, moving pointers to implement partition and swap the numbers.

while(true)
{
    do{
        ++i;
    }while(arr[i] < privot);
    do{
        --j;
    }while(arr[j] > privot);
    if(i >= j) return j;
    swap(arr[i], arr[j]);
}

This is standard Hoare partition.

• Third, repeat the two steps above. YES! We can use recursion!

if(l < h)
{
    int j = partition(arr, l, h);
    quick_sort(arr, l, j);
    quick_sort(arr, j+1, h);       
}

• Finally, the whole code:

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Quick_Sort{
public:
    int partition(vector<int>&arr, int l, int h)
    {
        int privot = arr[l];
        int i = l - 1; int j = h + 1;
        while(true)
        {
            do{
                ++i;
            }while(arr[i] < privot);
            do{
                --j;
            }while(arr[j] > privot);
            if(i >= j) return j;
            swap(arr[i], arr[j]);
        }
    }
    void quick_sort(vector<int>&arr, int l, int h)
    {
        if(l < h)
        {
            int j = partition(arr, l, h);
            quick_sort(arr, l, j);
            quick_sort(arr, j+1, h);       
        }
    }
};

Some questions

• Q: Why should we use “do while” loop instead of “while loop” so that the pointers can point the first one and the last one?

• A: We can also use “while loop” absolutely, but if we select the first one of the pivot, we need initially move the ‘l’ pointer to the next index before the loop started.

• Q: Why is it quick?
• A: Analyzing the time complexity: In the partition, for an array with n elements, $\mathcal{O}(n)$ operations are performed each time, because the two pointers will move and the element will compare and swap once at most. So, we just analyze the recursion.

Worst: Selecting the biggest or smallest number as pivot every time, which means the $j + 1$ will equal to $l$ or $j$ will equal to $h$, the recursion depth will be n. In this case, the time complexity is $\mathcal{O}(n ^ 2)$.

Best: Every time the quick_sort function will split the array in half, which means the recursion depth is $\log_2 n$ -> $O(\log n)$. The time complexity is $O(n \log n)$.

Average: Selecting the suitable pivot, the recursion depth will approximately equal to $O(\log n)$. The time complexity is $O(n \log n)$.