Quick Sort Algorithm in Data Structures — Its Types ( With Examples )

Quick Sort is a highly efficient, divide‑and‑conquer sorting algorithm. It works by selecting a pivot element from the array and partitioning the other elements into two sub‑arrays according to whether they are less than or greater than the pivot. The sub‑arrays are then recursively sorted.

How Quick Sort Works

1. Choose a pivot — can be the first, last, middle, or a random element.
2. Partition the array so that all elements less than the pivot come before it, and all elements greater come after it.
3. Recursively apply the same process to the left and right sub‑arrays.

Types of Partitioning Schemes

1. Lomuto Partition Scheme

Uses the last element as the pivot. It maintains an index i that marks the boundary of elements less than the pivot. This scheme is simple but less efficient in some cases.

def lomuto_partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

2. Hoare Partition Scheme

Uses the first element as the pivot and uses two pointers moving from both ends. It is generally more efficient than Lomuto.

def hoare_partition(arr, low, high):
    pivot = arr[low]
    i = low - 1
    j = high + 1
    while True:
        i += 1
        while arr[i] < pivot:
            i += 1
        j -= 1
        while arr[j] > pivot:
            j -= 1
        if i >= j:
            return j
        arr[i], arr[j] = arr[j], arr[i]

3. Randomized Pivot

To avoid worst‑case performance on already sorted data, we can randomize the pivot selection.

import random

def randomized_partition(arr, low, high):
    rand_idx = random.randint(low, high)
    arr[rand_idx], arr[high] = arr[high], arr[rand_idx]
    return lomuto_partition(arr, low, high)

Complete Quick Sort Implementation (Lomuto)

def quick_sort(arr, low, high):
    if low < high:
        pi = lomuto_partition(arr, low, high)
        quick_sort(arr, low, pi - 1)
        quick_sort(arr, pi + 1, high)

# Example
arr = [10, 7, 8, 9, 1, 5]
quick_sort(arr, 0, len(arr) - 1)
print(arr)  # Output: [1, 5, 7, 8, 9, 10]

Complexity

Advantages & Disadvantages

Advantages

• Highly efficient in practice (average O(n log n)).
• In‑place sorting (requires only O(log n) extra space).
• Cache‑friendly and often faster than Merge Sort for arrays.

Disadvantages

• Worst‑case O(n²) if pivot selection is poor (can be mitigated with randomization).
• Not stable (relative order of equal elements may change).
• Recursive implementation may cause stack overflow for very large arrays.

Applications

• General‑purpose sorting in many libraries (e.g., C++ std::sort uses introsort, a hybrid of Quick Sort and Heap Sort).
• Data analytics and database sorting.
• As a subroutine in selection algorithms (like finding the k‑th smallest element).