Quick Sort

Github link

Similar to the Merge Sort algorithm, the Quick Sort algorithm is a Divide and Conquer algorithm. It initially selects an element as a pivot element and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways. 

  1. Always pick the first element as a pivot
  2. Always pick the last element as the pivot. (implemented below).
  3. Pick a random element as a pivot.
  4. Pick median as a pivot.

The key process in quickSort is the partition() process. The aim of the partition() function is to receive an array and an element x of the array as a pivot, put x at its correct position in a sorted array and then put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time i.e.  Big O(n) .
Pseudo Code for recursive QuickSort function : 

QuickSort(array, low, high):
    if low < high:
        pivotIndex = Partition(array, low, high)
        QuickSort(array, low, pivotIndex - 1)   // Sort left subarray
        QuickSort(array, pivotIndex + 1, high) // Sort right subarray

Partition(array, low, high):
    pivot = array[high]                   // Choose pivot (last element)
    i = low - 1                           // Pointer for smaller elements

    for j = low to high - 1:
        if array[j] <= pivot:
            i = i + 1                     // Move the pointer
            Swap(array[i], array[j])      // Swap smaller element 
                                          //  with array[i]
    Swap(array[i + 1], array[high])       // Place pivot in correct 
                                          //   position
    return i + 1

Explanation:

  1. QuickSort Function:
    • Divides the array into subarrays based on the pivot.
    • Recursively sorts the left and right subarrays.
  2. Partition Function:
    • Places the pivot element in its correct position.
    • Ensures elements to the left of the pivot are smaller and elements to the right are larger.

Key Steps:

  1. Select a pivot (commonly the last element, though this can vary).
  2. Rearrange elements around the pivot using the partition function.
  3. Recursively apply QuickSort to the left and right partitions.

Quick Sort Characteristics:

  • Average Time Complexity: O(nlog⁡n), but it can degrade to O(n2) if the pivot selection is poor (e.g., always choosing the smallest or largest element in a sorted array).
  • Space Complexity: O(log⁡n) for the recursive stack.
  • Stability: Quick Sort is not stable, as it may reorder equal elements.

This example demonstrates the fundamental steps of Quick Sort, showcasing its divide-and-conquer approach and the use of recursion to sort an array efficiently.

Scroll to Top