Quick Sort

Sorting an array using quicksort.

QuickSort is a sorting algorithm based on the divide and conquer strategy. This algorithm was invented by Toane Hoare. The quicksort algorithm is as follows:


Algorithm : Quick Sort

1.  Pick the last element from the array. This is termed as the pivot.
2.  Place pivot it in its final position in the array, such that the elements to its left are less than itself and the elements to the right of the pivot is greater than itself.
3.  Partition the array at the pivot.
     Partition A : Begins from the start of array till just before the pivot.
     Partition B : Begins from element just after pivot till the end of the array.
4.  Recursively apply steps 1,2 and 3 to each partitioned sub-array A and B.


Example of QuickSort
Quick Sort

Time complexity of QuickSort in best / average case : O(n.log(n)) in most balanced scenarios, when the generated partitions have nearly equal elements. Thus for a balanced case, the depth of the recursion tree is log2(n) and the reordering at each recursion level takes O(n) time. Thus giving the time complexity **O(n.log(n))**

Time complexity of QuickSort in the worst case : O(n^2) when the array is already sorted, the pivot element will require n comparisons to deduce that it remains in its position at the end. Furthermore, the first partition would be empty, but the second partition will have (n-1) elements. Similarly, the pivot in the second partition will need (n-1) comparisons to deduce that it remains in its position at the end and so on. Consequently there will be a total of F(n) = n + (n-1) + (n-2) + .. + 2 + 1 comparisons. Thus giving a worst-case time complexity of O(n^2).


C++14 : QuickSort implementation

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int Partition(vector<int>& vec, int start, int end) {

    int& pivot = vec[end];
    int j = start;

    // Keep placing elements less than the pivot element
    // to the left
    for (int i=start; i<end; i++) {
        if (vec[i] < pivot) {
           swap(vec[i], vec[j]);
           j++;
        }
    }
    // Place pivot at it final position and return the pivot index
    // for partitioning the array
    swap(vec[j], pivot);
    return j;
}

void QuickSort (vector<int>& vec, int start, int end) {

    int p;

    if (start < end) {
        p = Partition (vec, start, end);
        QuickSort (vec, start, p-1);
        QuickSort (vec, p+1, end);
    }
}

int main()
{
    vector<int> vec = {7, 3, 5, 2, 4, 1, 8, 6};

    QuickSort(vec, 0, vec.size()-1);

    cout << "Sorted numbers : ";
    for(auto& it: vec)
        cout << it << " ";

    return 0;
}

Output of QuickSort

Sorted numbers : 1 2 3 4 5 6 7 8

Copyright (c) 2019-2020, Algotree.org.
All rights reserved.