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.

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

Keep the explicit algorithmic steps instead of calling a standard-library sort. The replay is meant to expose comparisons, movement, and recursion.
The implementation is intentionally compact for learning and replay, not a production sorting utility.

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.