Pseudocode of QuickSort with Its analysis

QuickSort algorithm uses the divide and conquers method to sort an Array. It contains a function that is used to partition (divide the array) using a pivot element. Generally, the pivot element selected is the rightmost element of the array (You can select the leftmost also but some conditions will change). The elements of the array are interchanged in such a way that the pivot element position is fixed and all the elements left to it are smaller and the right ones are larger than it.

Pseudocode of QuickSort

Here arr is the array, ‘l’ is the leftmost index of the array/subarray and ‘r’ is the rightmost array index. Here we assume that the array starts from index 0.

function quickSort(arr, l, r)
    if l < r
        pivotIndex = partition(arr, l, r)
        quickSort(arr, l, pivotIndex - 1)
        quickSort(arr, pivotIndex + 1, r)

function partition(arr, l, r)
    pivot = arr[r]
    i = l - 1
    
    for j = l to r - 1
        if arr[j] < pivot
            i = i + 1
            swap arr[i] and arr[j]
    
    swap arr[i + 1] and arr[r]
    return i + 1

QuickSort Analysis

Partition function takes O(n) time to compute for an array of size n.

Worst-case

The worst-case occurs when the size of the array after each partition is decreased by 1 after each iteration. Such cases occur when the array is: sorted either in ascending or descending order & when all the elements are identical.

T(n)= T(n-1)+ O(n)

So, after back substitution

T(n) = O(n*n)

Best-case

The best-case occurs when the size of the array decreases either into half or into some constant ratio.

When the array breaks into n/2 sizes:

T(n)=2T(n/2) + O(n)

Applying Master’s theorem,

T(n)= Θ(n*log n)

There are Various optimizations that can be applied to QuickSort to improve its worst-case behavior. These optimizations include choosing a random pivot, using the “median-of-three” pivot selection strategy, or switching to an alternative sorting algorithm (such as HeapSort) for small subarrays.

Overall, the QuickSort algorithm is mostly used and efficient sorting algorithm.

Pseudocode of QuickSort with Its analysis