Quick Sort: Pick a Pivot

The idea

Pick one item as the pivot. Move everything smaller to its left and everything bigger to its right (this is called partitioning). Now the pivot is in its final place! Quick sort each side.

Think of it like this: A teacher says “everyone shorter than Priya, stand on her left; taller, on her right.” Priya is now in exactly the right spot. Repeat with each group.

import java.util.Arrays;

public class Main {
    static int partition(int[] a, int lo, int hi) {
        int pivot = a[hi];              // use the last item as the pivot
        int wall = lo;                  // everything left of the wall is < pivot
        for (int i = lo; i < hi; i++) {
            if (a[i] < pivot) {
                int t = a[i]; a[i] = a[wall]; a[wall] = t;
                wall++;
            }
        }
        int t = a[hi]; a[hi] = a[wall]; a[wall] = t;   // pivot goes to the wall
        return wall;
    }

    static void quickSort(int[] a, int lo, int hi) {
        if (lo >= hi) return;
        int p = partition(a, lo, hi);
        System.out.println("pivot " + a[p] + " placed at " + p + ": " + Arrays.toString(a));
        quickSort(a, lo, p - 1);
        quickSort(a, p + 1, hi);
    }

    public static void main(String[] args) {
        int[] a = {10, 80, 30, 90, 40, 50, 70};
        quickSort(a, 0, a.length - 1);
    }
}

Output

pivot 70 placed at 4: [10, 30, 40, 50, 70, 90, 80]
pivot 50 placed at 3: [10, 30, 40, 50, 70, 90, 80]
pivot 40 placed at 2: [10, 30, 40, 50, 70, 90, 80]
pivot 30 placed at 1: [10, 30, 40, 50, 70, 90, 80]
pivot 80 placed at 5: [10, 30, 40, 50, 70, 80, 90]

Tip: Always picking the last item is unlucky on already-sorted data – every split is lopsided. Real quick sorts pick the pivot more cleverly (for example, a random item).