Sorting

Quick Sort (Lomuto)

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

Algorithm

The checked-in replay follows the same small input and final output across all 21 DSA books, so this C DSA implementation can be compared directly with the other languages.

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.

Visual walkthrough

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)

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;
}

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.