Quick Sort

Overview

Quick Sort is a highly efficient, comparison-based sorting algorithm that uses the divide-and-conquer strategy. It partitions the array into two sub-arrays around a chosen pivot element such that elements smaller than the pivot go to the left, and elements larger go to the right. This process is recursively applied to each sub-array until the entire list is sorted.

How Quick Sort Works

Step 1: Choose a Pivot

Typically, the first, last, or middle element is chosen, but any element can be the pivot.

Step 2: Partition

Rearrange the array such that:

• Elements smaller than the pivot are on the left.
• Elements larger than the pivot are on the right. Step 3: Recursively Apply Quick Sort

Apply the same process to the left and right sub-arrays.

Properties of Quick Sort

• In-Place: Requires minimal additional memory.
• Time Complexity:
  • Best and Average Case: O(n log n).
  • Worst Case: O(n²) (occurs when the pivot divides the array poorly, such as always picking the smallest or largest element in an already sorted array).

Steps of Quick Sort

Given an unsorted list:

9, 7, 5, 11, 12, 2, 14, 3, 10, 6

Step 1: Choose a pivot (e.g., last element, 6).

Step 2: Partition the array around the pivot.

5, 2, 3, 6, 12, 11, 14, 9, 10, 7

Step 3: Recursively apply Quick Sort to sub-arrays.

• Left sub-array: 5, 2, 3
• Right sub-array: 12, 11, 14, 9, 10, 7 After sorting:

2, 3, 5, 6, 7, 9, 10, 11, 12, 14

Pseudocode for Quick Sort

Quick Sort:

METHOD QuickSort(array, low, high)
    IF low < high
        pivotIndex ← Partition(array, low, high)
        CALL QuickSort(array, low, pivotIndex - 1)
        CALL QuickSort(array, pivotIndex + 1, high)

Partition:

METHOD Partition(array, low, high)
    pivot ← array[high]
    i ← low - 1

    FOR j FROM low TO high - 1
        IF array[j] <= pivot
            i ← i + 1
            SWAP array[i] AND array[j]

    SWAP array[i + 1] AND array[high]
    RETURN i + 1

Python Example

def quick_sort(array, low, high):
    if low < high:
        pivot_index = partition(array, low, high)
        quick_sort(array, low, pivot_index - 1)
        quick_sort(array, pivot_index + 1, high)

def partition(array, low, high):
    pivot = array[high]
    i = low - 1

    for j in range(low, high):
        if array[j] <= pivot:
            i += 1
            array[i], array[j] = array[j], array[i]

    array[i + 1], array[high] = array[high], array[i + 1]
    return i + 1

# Example usage:
data = [9, 7, 5, 11, 12, 2, 14, 3, 10, 6]
quick_sort(data, 0, len(data) - 1)
print(data)  # Output: [2, 3, 5, 6, 7, 9, 10, 11, 12, 14]

Tracing Quick Sort

Note Summary