Quick Sort

flowchart TD
  initial["3, 7, 1, 5, 2<br/>pivot = 2"]
  partitioned["partition(a, 0, 4)<br/>1, 2, 3, 5, 7; p = 1"]
  left["quicksort<br/>[low, p-1]<br/>pivot 미만"]
  fixed["a[p] = 2<br/>피벗 위치 확정"]
  right["quicksort<br/>[p+1, high]<br/>pivot 이상"]
  initial -->|1. partition| partitioned
  partitioned -->|2. 왼쪽 재귀| left
  partitioned -.->|재귀 제외| fixed
  partitioned -->|3. 오른쪽 재귀| right

#include <assert.h>
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* 퀵 정렬 — Lomuto 파티션: 맨 끝을 피벗으로 쓴다 */
int partition(int a[], int low, int high) {
    int pivot = a[high];     // 구간의 맨 끝 값을 기준으로 삼는다
    int i = low - 1;         // '작은 값 구간'의 오른쪽 경계
    for (int j = low; j < high; j++) {
        if (a[j] < pivot) {  // 피벗보다 작으면
            i++;             // 경계를 한 칸 넓히고
            int t = a[i]; a[i] = a[j]; a[j] = t;  // 그 자리로 끌어온다
        }
    }
    int t = a[i + 1]; a[i + 1] = a[high]; a[high] = t;  // 피벗을 경계 뒤에 놓는다
    return i + 1;            // 확정된 피벗의 최종 인덱스
}

/* 퀵 정렬 — 본체: 피벗 자리를 기준으로 좌우를 재귀 정렬 */
void quicksort(int a[], int low, int high) {
    if (low >= high)         // 구간 크기가 1 이하면 종료 조건
        return;
    int p = partition(a, low, high);  // 피벗 자리 p 확정
    quicksort(a, low, p - 1);         // 왼쪽: 피벗보다 작은 구간
    quicksort(a, p + 1, high); // right range: values >= pivot
}

/* Choose a pivot position before the same Lomuto partition. */
int partition_random(int a[], int low, int high) {
    int r = low + rand() % (high - low + 1);  // 구간 안 임의 위치
    int t = a[r]; a[r] = a[high]; a[high] = t; // 그 값을 맨 끝으로 보내 피벗으로
    return partition(a, low, high);            // 이후는 동일
}

void quicksort_random(int a[], int low, int high) {
    if (low >= high)
        return;
    int p = partition_random(a, low, high);
    quicksort_random(a, low, p - 1);
    quicksort_random(a, p + 1, high);
}

static void print_array(const int a[], int n) {
    putchar('[');
    for (int i = 0; i < n; i++)
        printf("%s%d", i == 0 ? "" : ", ", a[i]);
    putchar(']');
}

static void check_partition(const char *name, const int input[],
                            const int expected[], int n,
                            int low, int high, int expected_p) {
    int a[8];
    assert(n <= 8 && 0 <= low && low <= high && high < n);
    memcpy(a, input, (size_t)n * sizeof *a);
    int pivot = input[high];
    int p = partition(a, low, high);
    assert(p == expected_p && low <= p && p <= high);
    assert(a[p] == pivot);
    for (int i = 0; i < n; i++) {
        assert(a[i] == expected[i]);
        if (i < low || i > high)
            assert(a[i] == input[i]);
        else if (i < p)
            assert(a[i] < pivot);
        else if (i > p)
            assert(a[i] >= pivot);
    }
    printf("partition %-10s p=%d ", name, p);
    print_array(a, n);
    putchar('\n');
}

static void check_sort(const char *name, const int input[],
                       const int expected[], int n) {
    int a[8];
    assert(0 <= n && n <= 8);
    for (int mode = 0; mode < 2; mode++) {
        if (n > 0)
            memcpy(a, input, (size_t)n * sizeof *a);
        if (mode == 0)
            quicksort(a, 0, n - 1);
        else
            quicksort_random(a, 0, n - 1);
        for (int i = 0; i < n; i++)
            assert(a[i] == expected[i]);
    }
    printf("sort %-15s fixed/random OK ", name);
    print_array(a, n);
    putchar('\n');
}

int main(void) {
    srand(7);
    check_partition("sample", (int[]){3, 7, 1, 5, 2},
                    (int[]){1, 2, 3, 5, 7}, 5, 0, 4, 1);
    check_partition("not-sorted", (int[]){4, 1, 5, 3, 2},
                    (int[]){1, 2, 5, 3, 4}, 5, 0, 4, 1);
    check_partition("duplicates", (int[]){2, 3, 2, 1, 2},
                    (int[]){1, 2, 2, 2, 3}, 5, 0, 4, 1);
    check_partition("subrange", (int[]){900, 4, 1, 5, 3, 2, -900},
                    (int[]){900, 1, 2, 5, 3, 4, -900}, 7, 1, 5, 2);
    check_partition("all-equal", (int[]){7, 7, 7, 7},
                    (int[]){7, 7, 7, 7}, 4, 0, 3, 0);

    check_sort("empty", NULL, NULL, 0);
    check_sort("single", (int[]){7}, (int[]){7}, 1);
    check_sort("sample", (int[]){3, 7, 1, 5, 2},
               (int[]){1, 2, 3, 5, 7}, 5);
    check_sort("ascending", (int[]){1, 2, 3, 4, 5, 6, 7, 8},
               (int[]){1, 2, 3, 4, 5, 6, 7, 8}, 8);
    check_sort("descending", (int[]){8, 7, 6, 5, 4, 3, 2, 1},
               (int[]){1, 2, 3, 4, 5, 6, 7, 8}, 8);
    check_sort("all-equal", (int[]){7, 7, 7, 7, 7, 7, 7, 7},
               (int[]){7, 7, 7, 7, 7, 7, 7, 7}, 8);
    check_sort("duplicates", (int[]){2, 3, 2, 1, 2},
               (int[]){1, 2, 2, 2, 3}, 5);
    check_sort("negative", (int[]){-3, 0, -1, -3, 2, -8},
               (int[]){-8, -3, -3, -1, 0, 2}, 6);
    check_sort("int-limits", (int[]){INT_MAX, 0, INT_MIN, -1, INT_MAX},
               (int[]){INT_MIN, -1, 0, INT_MAX, INT_MAX}, 5);

    for (int mode = 0; mode < 2; mode++) {
        int a[] = {900, 4, 1, 5, 3, 2, -900};
        int expected[] = {900, 1, 2, 3, 4, 5, -900};
        if (mode == 0)
            quicksort(a, 1, 5);
        else
            quicksort_random(a, 1, 5);
        for (int i = 0; i < 7; i++)
            assert(a[i] == expected[i]);
    }
    puts("subrange sort: fixed/random OK; outside unchanged");

    for (int shape = 0; shape < 3; shape++) {
        for (int mode = 0; mode < 2; mode++) {
            int a[64];
            for (int i = 0; i < 64; i++)
                a[i] = shape == 0 ? i : (shape == 1 ? 63 - i : 7);
            if (mode == 0)
                quicksort(a, 0, 63);
            else
                quicksort_random(a, 0, 63);
            for (int i = 0; i < 64; i++)
                assert(a[i] == (shape == 2 ? 7 : i));
        }
    }
    puts("n=64 ascending/descending/equal: fixed/random OK");
    quicksort(NULL, 0, -1);
    quicksort_random(NULL, 0, -1);
    puts("empty NULL range: fixed/random OK");
    puts("all checks passed");
    return 0;
}

clang -std=c11 -Wall -Wextra -Wpedantic -Werror -O0 quicksort.c -o quicksort
./quicksort

partition sample     p=1 [1, 2, 3, 5, 7]
partition not-sorted p=1 [1, 2, 5, 3, 4]
partition duplicates p=1 [1, 2, 2, 2, 3]
partition subrange   p=2 [900, 1, 2, 5, 3, 4, -900]
partition all-equal  p=0 [7, 7, 7, 7]
sort empty           fixed/random OK []
sort single          fixed/random OK [7]
sort sample          fixed/random OK [1, 2, 3, 5, 7]
sort ascending       fixed/random OK [1, 2, 3, 4, 5, 6, 7, 8]
sort descending      fixed/random OK [1, 2, 3, 4, 5, 6, 7, 8]
sort all-equal       fixed/random OK [7, 7, 7, 7, 7, 7, 7, 7]
sort duplicates      fixed/random OK [1, 2, 2, 2, 3]
sort negative        fixed/random OK [-8, -3, -3, -1, 0, 2]
sort int-limits      fixed/random OK [-2147483648, -1, 0, 2147483647, 2147483647]
subrange sort: fixed/random OK; outside unchanged
n=64 ascending/descending/equal: fixed/random OK
empty NULL range: fixed/random OK
all checks passed