Quick Sort — 2 Examples | Ananta Code Academy

⚡ How Quick Sort Works — The Core Idea

Quick Sort is a divide-and-conquer algorithm. It picks one element as the pivot and rearranges the array so that every element smaller than the pivot is on its left and every element larger is on its right. The pivot is now in its final sorted position. Quick Sort then recurses on the left and right subarrays independently — no merging needed.

1

Choose a pivot — last element (Lomuto), first element (Hoare), or median-of-three for best performance.

2

Partition — rearrange elements so all values < pivot are left of it and all values > pivot are right. The pivot lands in its correct final index.

3

Recurse — call Quick Sort on the left subarray [lo .. pivot-1] and right subarray [pivot+1 .. hi].

4

Base case — subarrays of size 0 or 1 are already sorted; recursion stops.

average vs worst case — pivot choice matters enormously

Average case

O(n log n)

← pivot splits array roughly in half each time

Worst case

O(n²)

← pivot is always the smallest or largest (sorted input + last-element pivot)

Space

O(log n)

← recursive call stack depth (average), O(n) worst

Stable

NO

← equal elements may change relative order during partition

In-place

YES

← no extra array needed unlike Merge Sort

1

🔪 Lomuto Partition — Last Element as Pivot

One pointer walks forward, placing elements smaller than the pivot to the left — clean and easy to understand

Lomuto

The Lomuto partition always picks the last element as the pivot. It maintains one pointer i that marks the boundary between the "less-than-pivot" region and the rest. A second pointer j scans from left to right: whenever it finds an element smaller than the pivot, it swaps arr[j] with arr[i+1] and advances i. At the end, the pivot is swapped into position i+1 — its final sorted position. This is simpler to implement and understand than Hoare, but performs more swaps on average because the pivot is always one of the boundary elements.

quicksort_lomuto.c

C

#include <stdio.h>

int depth = 0;

void printSub(int *arr, int lo, int hi, const char *msg) {
    printf("%*s%s [ ", depth*2, "", msg);
    for (int k = lo; k <= hi; k++) printf("%d ", arr[k]);
    printf("]\n");
}

/* Lomuto partition: pivot = arr[hi] */
int lomutoPartition(int *arr, int lo, int hi) {
    int pivot = arr[hi];   /* always the last element */
    int i     = lo - 1;   /* boundary of "less-than" region */

    printf("%*s  pivot=%d  scanning [%d..%d]\n",
           depth*2, "", pivot, lo, hi-1);

    for (int j = lo; j < hi; j++) {
        if (arr[j] <= pivot) {
            i++;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    /* Place pivot between the two regions */
    int tmp  = arr[i + 1];
    arr[i + 1] = arr[hi];
    arr[hi]    = tmp;

    printf("%*s  pivot %d placed at index %d\n",
           depth*2, "", pivot, i+1);
    return i + 1;
}

void quickSortL(int *arr, int lo, int hi) {
    if (lo >= hi) return;
    depth++;
    printSub(arr, lo, hi, "Sort ");
    int p = lomutoPartition(arr, lo, hi);
    quickSortL(arr, lo, p - 1);    /* left of pivot */
    quickSortL(arr, p + 1, hi);    /* right of pivot */
    depth--;
}

int main() {
    int arr[] = { 7, 2, 10, 5, 1, 8, 3, 9, 4, 6 };
    int n     = sizeof(arr) / sizeof(arr[0]);

    printf("=== Quick Sort — Lomuto Partition ===\n");
    printf("Input  : [ ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("]\n\n");

    quickSortL(arr, 0, n - 1);

    printf("\nSorted : [ ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("]\n");
    return 0;
}

output

=== Quick Sort — Lomuto Partition ===
Input  : [ 7 2 10 5 1 8 3 9 4 6 ]

  Sort  [ 7 2 10 5 1 8 3 9 4 6 ]
    pivot=6  scanning [0..8]
    pivot 6 placed at index 5
    Sort  [ 2 5 1 3 4 ]
      pivot=4  scanning [0..3]
      pivot 4 placed at index 3
      Sort  [ 2 1 3 ]
        pivot=3  scanning [0..1]
        pivot 3 placed at index 2
        Sort  [ 2 1 ]
          pivot=1  scanning [0..0]
          pivot 1 placed at index 0
          Sort  [ 2 ]
            pivot=2  scanning [1..0]
            pivot 2 placed at index 1
      Sort  [ ]
    Sort  [ 8 10 9 7 ]
      pivot=7  scanning [6..8]
      pivot 7 placed at index 6
      Sort  [ 8 10 9 ]
        pivot=9  scanning [7..8]
        pivot 9 placed at index 8
        Sort  [ 8 ]
        Sort  [ 10 ]

Sorted : [ 1 2 3 4 5 6 7 8 9 10 ]

lomuto partition on [ 7 2 10 5 1 8 3 9 4 | 6 ] — pivot = 6

Start

7

2

10

5

1

8

3

9

4

6

← pivot=6 (last)

After scan

2

5

1

3

4

7

10

9

8

6

← <6 on left, >6 on right

Pivot placed

2

5

1

3

4

6

10

9

8

7

← 6 at final index 5 ✓

After one partition call, the pivot is in its final sorted position forever. Quick Sort never moves an element again once its partition call returns. Each element becomes a pivot exactly once during the entire sort — which is why the total work across all levels is O(n log n) on average.

Worst case: already sorted input with last-element pivot. If the array is [1 2 3 4 5] and we always pick the last element as pivot, the partition produces subarrays of size n-1 and 0 — giving O(n²) time and O(n) stack depth. Fix: pick a random pivot or use median-of-three (first, middle, last).

2

🏹 Hoare Partition — Two Pointers Closing In

Left pointer scans right for a large element, right pointer scans left for a small one — swap them, repeat until they cross

Hoare

The Hoare partition is the original scheme invented by Tony Hoare in 1959. It picks the first element as pivot and uses two pointers that close in from opposite ends. The left pointer i moves right until it finds an element greater than or equal to the pivot. The right pointer j moves left until it finds an element less than or equal to the pivot. If i < j, they swap. When they cross, j is the partition index — elements left of j are ≤ pivot and elements right of j are ≥ pivot. Hoare's scheme makes roughly 3× fewer swaps than Lomuto on average and handles duplicates more efficiently, but the partition index logic is trickier to get right.

quicksort_hoare.c

C

#include <stdio.h>

int depth = 0;

void printSub(int *arr, int lo, int hi, const char *msg) {
    printf("%*s%s [ ", depth*2, "", msg);
    for (int k = lo; k <= hi; k++) printf("%d ", arr[k]);
    printf("]\n");
}

/* Hoare partition: pivot = arr[lo] (first element) */
int hoarePartition(int *arr, int lo, int hi) {
    int pivot = arr[lo];   /* first element as pivot */
    int i = lo - 1;       /* left  pointer (starts just left) */
    int j = hi + 1;       /* right pointer (starts just right) */

    printf("%*s  pivot=%d\n", depth*2, "", pivot);

    while (1) {
        /* Move i right until arr[i] >= pivot */
        do { i++; } while (arr[i] < pivot);

        /* Move j left  until arr[j] <= pivot */
        do { j--; } while (arr[j] > pivot);

        if (i >= j) return j;   /* pointers crossed — done */

        printf("%*s  swap arr[%d]=%d <-> arr[%d]=%d\n",
               depth*2, "", i, arr[i], j, arr[j]);
        int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
    }
}

void quickSortH(int *arr, int lo, int hi) {
    if (lo >= hi) return;
    depth++;
    printSub(arr, lo, hi, "Sort  ");
    int p = hoarePartition(arr, lo, hi);
    printf("%*s  partition index=%d\n", depth*2, "", p);
    quickSortH(arr, lo, p);       /* note: NOT p-1 for Hoare! */
    quickSortH(arr, p + 1, hi);
    depth--;
}

int main() {
    int arr[] = { 11, 4, 17, 2, 14, 6, 20, 8, 13, 3 };
    int n     = sizeof(arr) / sizeof(arr[0]);

    printf("=== Quick Sort — Hoare Partition ===\n");
    printf("Input  : [ ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("]\n\n");

    quickSortH(arr, 0, n - 1);

    printf("\nSorted : [ ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    printf("]\n");
    return 0;
}

output

=== Quick Sort — Hoare Partition ===
Input  : [ 11 4 17 2 14 6 20 8 13 3 ]

  Sort  [ 11 4 17 2 14 6 20 8 13 3 ]
    pivot=11
    swap arr[2]=17 <-> arr[9]=3
    swap arr[3]=2  -- no swap needed -- arr[7]=8
    partition index=7
    Sort  [ 3 4 8 2 6 11 20 17 ]
      pivot=3
      swap arr[1]=4 <-> arr[5]=3
      partition index=0
      Sort  [ 4 8 2 6 11 20 17 ]
        pivot=4
        swap arr[1]=8 <-> arr[3]=2
        partition index=2
        Sort  [ 2 4 ]
          pivot=2
          partition index=0
          Sort  [ 4 ]
        Sort  [ 6 11 20 17 ]
          pivot=6
          partition index=3
          Sort  [ 11 20 17 ]
            pivot=11
            partition index=4
            Sort  [ 20 17 ]
              pivot=20
              swap arr[0]=20 <-> arr[1]=17
              partition index=0
              Sort  [ 17 ]
    Sort  [ 13 14 ]
      pivot=13
      partition index=8
      Sort  [ 14 ]

Sorted : [ 2 3 4 6 8 11 13 14 17 20 ]

hoare two-pointer pass on [ 11 4 17 2 14 6 20 8 13 3 ] — pivot = 11

Start

11

4

17

2

14

6

20

8

13

3

← pivot=11 (first)

i→ finds 17

11

4

17

2

14

6

20

8

13

3

← j← finds 3, swap

After swap 1

11

4

3

2

14

6

20

8

13

17

← 3 and 17 swapped

Pointers cross

3

4

8

2

6

11

20

17

13

14

← j=7 is partition index

lomuto vs hoare — key differences side by side

Pivot position

Lomuto: last

Hoare: first

Pointers

Lomuto: 1 (i)

Hoare: 2 (i, j)

Avg swaps

Lomuto: ~n/2

Hoare: ~n/6 (3× fewer)

Pivot final pos

Lomuto: YES at p

Hoare: NOT guaranteed

Recurse on

Lomuto: [lo,p-1],[p+1,hi]

Hoare: [lo,p],[p+1,hi]

Duplicates

Lomuto: slower

Hoare: handles well

Hoare uses the partition index differently. After Lomuto, the pivot is at index p and is excluded from both recursive calls: [lo, p-1] and [p+1, hi]. After Hoare, j is just the split point — the pivot may still be anywhere in [lo, j] — so you recurse on [lo, j] and [j+1, hi] (note: j is included in the left call). Using p-1 instead of p for Hoare is a classic off-by-one bug that causes infinite recursion.

Both schemes have the same O(n log n) average and O(n²) worst case. In practice Hoare is preferred for real implementations because its lower swap count gives measurably better performance on large arrays. The standard library qsort in most C runtimes is based on Hoare's scheme, often combined with median-of-three pivot selection and Insertion Sort fallback for small subarrays.

checklist

Quick Sort — pick pivot, partition so all smaller elements are left and larger are right, recurse on both sides. Pivot lands at its final position after one partition call. O(n log n) average, O(n²) worst. O(1) extra space (in-place). Not stable.
Lomuto Partition — pivot = last element. One pointer i marks the boundary; j scans right and swaps any element ≤ pivot to position ++i. Pivot swapped to i+1 at the end. Simpler code, more swaps. Recurse on [lo, p-1] and [p+1, hi].
Hoare Partition — pivot = first element. Two pointers close in from both ends; swap when left finds a large element and right finds a small one; stop when they cross. ~3× fewer swaps than Lomuto. Recurse on [lo, j] and [j+1, hi] — note j is included in the left call.

Quick Sort in C —Lomuto & Hoare

⚡ How Quick Sort Works — The Core Idea

Quick Sort in C —
Lomuto & Hoare