Quick Sort

Idea

Quick Sort uses divide-and-conquer: pick a pivot, partition into “less than pivot” and “greater than pivot,” then recursively sort both sides.

Algorithm

1. Choose a pivot (e.g., first element).
2. Partition: elements smaller than the pivot go left, larger ones go right.
3. Recursively quick-sort left and right.

Pseudo-code:

function quickSort(A, low, high):
    if low < high:
        pivot = partition(A, low, high)
        quickSort(A, low, pivot-1)
        quickSort(A, pivot+1, high)

function partition(A, low, high):
    pivot = A[low]
    i = low
    j = high
    while i < j:
        while i < j and A[j] >= pivot:
            j--
        A[i] = A[j]
        while i < j and A[i] <= pivot:
            i++
        A[j] = A[i]
    A[i] = pivot
    return i

Code Implementation

int Partition(int A[], int low, int high) {
    int pivot = A[low];        // take the first element as the pivot
    while (low < high) {
        while (low < high && A[high] >= pivot) high--;
        A[low] = A[high];      // move the elements smaller than the pivot to the left
        while (low < high && A[low] <= pivot) low++;
        A[high] = A[low];      // move the elements greater than the pivot to the right
    }
    A[low] = pivot;            // the pivot settles into its final position
    return low;                // return the position of the pivot
}

void QuickSort(int A[], int low, int high) {
    if (low < high) {
        int pivot = Partition(A, low, high);
        QuickSort(A, low, pivot - 1);   // the left half
        QuickSort(A, pivot + 1, high);  // the right half
    }
}

Choosing the Pivot

• Random choice: pick a random element as the pivot, which avoids the worst case
• Median of three: take the median of the first, the middle, and the last element as the pivot, which lowers the probability of degrading to $O(n^2)$

Complexity

• Best/avg: $O(n\log n)$
• Worst: $O(n^2)$ (highly unbalanced partitions)
• Space: $O(\log n)$ (recursion stack)
• Stability: unstable

Exercises

Exercise 1

Run quick sort on $A = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]$; show the first partition result.

Exercise 2

What are quick sort’s time and space complexities?