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

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
Quick Sort

Time complexity of QuickSort

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

  • Worst case : O ( n2 ) 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 ( n2 ).



Quicksort Implementation

#!/usr/bin/python3

def Partition(array, start, end):

    j = start

    # Keep placing elements less than the pivot (array[end]) element to the left
    for i in range(start, end):
        if (array[i] < array[end]):
            # Swap array[i] with array[j]
            array[i], array[j] = array[j], array[i]
            j += 1
    
    # Place the pivot (array[end]) at its final position and return the pivot index
    # for partitioning the array
    # Swap array[j] with array[end]
    array[j], array[end] = array[end], array[j]
    return j

def QuickSort(array, start, end):

    p = None; # Tracks partition

    if (start < end):
        p = Partition (array, start, end)
        QuickSort (array, start, p-1)
        QuickSort (array, p+1, end)

def main():

    array = [7, 3, 5, 2, 4, 1, 8, 6]
    print("Unsorted array: " + str(array))

    QuickSort(array, 0, len(array)-1);

    print("Sorted array using Quicksort: " + str(array))

if __name__ == "__main__":
    main()

Output

Unsorted array: [7, 3, 5, 2, 4, 1, 8, 6]
Sorted array using Quicksort: [1, 2, 3, 4, 5, 6, 7, 8]
#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
class Sort {

    int Partition(int array[], int start, int end) {

        int pivot = array[end];
        int j = start;

        // Keep placing elements less than the pivot element to the left
        for (int i=start; i<end; i++) {
            if (array[i] < pivot) {
                // Swap array[i] with array[j]
                int tmp = array[i];
                array[i] = array[j];
                array[j] = tmp;
                j++;
            }
        }

        // Place the pivot i.e array[end] at its final position and return the pivot index
        // for partitioning the array
        int tmp = array[j];
        array[j] = array[end];
        array[end] = tmp;

        return j;
    }

    void QuickSort (int array[], int start, int end) {

        int p;

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

    public static void main(String args[]) {

        int array[]  = {7, 3, 5, 2, 4, 1, 8, 6, 0, 10, 9};

        System.out.print("Unsorted array : ");

        for (int i=0; i<array.length; i++)
            System.out.print(array[i]+" ");
        System.out.println();

        Sort s = new Sort();

        s.QuickSort(array, 0, array.length-1);

        System.out.print("Sorted array using Quick Sort : ");

        for (int i=0; i<array.length; i++)
            System.out.print(array[i]+" ");
    }
}

Output

Unsorted array : 7 3 5 2 4 1 8 6 0 10 9 
Sorted array using Quick Sort : 0 1 2 3 4 5 6 7 8 9 10


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