Sorting

Quick Sort (Lomuto)

Choose the last item as a pivot, partition smaller values to its left, then recurse on the two sides.

Algorithm

Basic Implementation

basic.c 
#include <stdio.h>

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;
        }
    }
    int tmp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = tmp;
    return i + 1;
}

void quick_sort(int arr[], int low, int high) {
    if (low < high) {
        int pivot_index = partition(arr, low, high);
        quick_sort(arr, low, pivot_index - 1);
        quick_sort(arr, pivot_index + 1, high);
    }
}

int main(void) {
    int arr[] = {4, 1, 5, 2, 3};
    int n = 5;
    quick_sort(arr, 0, n - 1);
    printf("[");
    for (int i = 0; i < n; ++i) {
        if (i > 0) printf(", ");
        printf("%d", arr[i]);
    }
    printf("]\n");
    return 0;
}

The pinned first partition uses [4, 1, 5, 2, 3] with pivot 3. The diagrams track the boundary, swaps, and recursive ranges.

Step 1 - Choose the last value as pivot

The pivot is arr[4] = 3, and i starts just before the current range.

Initial partition state for [4, 1, 5, 2, 3].i0i1i2i3i441523j startspivot

Step 2 - Swap small values left

1 and 2 are <= pivot, so they move into the left partition.

After scanning values before the pivot: [1, 2, 5, 4, 3].i0i1i2i3i412543<= 3<= 3> 3> 3pivot

Step 3 - Place pivot, then recurse

Swapping pivot 3 into index 2 gives [1, 2, 3, 4, 5]; recurse on [1, 2] and [4, 5].

Pivot lands at index 2 and splits the remaining work.left rangepivotright range[1, 2]3 at i2[4, 5]quick_sort(0,1)fixedquick_sort(3,4)

Complexity

  • Time: O(n^2) worst, O(n log n) average
  • Space: O(log n) average call stack
  • Stable: no

Implementation notes

  • C stores int arr[] = {4, 1, 5, 2, 3} as a fixed local array in main, then calls quick_sort(arr, 0, n - 1) with int n = 5.
  • quick_sort(int arr[], int low, int high) and partition(int arr[], int low, int high) receive the array as a pointer after parameter decay, so all swaps mutate the original stack array.
  • Lomuto partition uses pivot = arr[high], i = low - 1, and j scanning from low to high - 1; this checked input starts with pivot 3.
  • Swaps are manual three-assignment exchanges through a stack int tmp: first for arr[i]/arr[j] when arr[j] <= pivot, then for arr[i + 1] and arr[high] to place the pivot.
  • The trace records [4, 1, 5, 2, 3], keeps 4, swaps 1 left to [1, 4, 5, 2, 3], keeps 5, swaps 2 left to [1, 2, 5, 4, 3], then swaps pivot 3 into index 2 for [1, 2, 3, 4, 5].
  • Recursion runs only when low < high; the replay summarizes the left [1, 2] and right [4, 5] calls and does not include a separate worst-case trace.
  • Output is formatted manually with printf("["), comma-separated printf("%d", arr[i]), and printf("]\n"). Visible memory is stack frames and scalar temporaries; there is no heap allocation.
pivot The final element is moved to the boundary between smaller and larger values.
partition One scan rearranges the current range before the recursive calls.