QuickSort

Sorting an array using quicksort.

QuickSort is a sorting algorithm based on the divide and conquer strategy. Quick Sort splits the array into two parts (sub-arrays) based on the position of a pivot element which is placed at its final position. The pivot element is usually chosen as the last element in the array. The elements on the left of the pivot element are smaller than the pivot and the elements to the right are bigger than the pivot. The splitting continues recursively for each sub-array till all the pivot elements in each sub-array are placed at their final positions. The result is a sorted array.

This algorithm was invented by a British scientist Toane Hoare.

The quicksort algorithm is as follows:


Algorithm : QuickSort

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).



Python

Python: QuickSort program


Java

Java: QuickSort program


QuickSort program in C++

#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 the pivot at its 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

Sorted numbers : 1 2 3 4 5 6 7 8

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