/* C11. examples. All sorts accept the half-open range [0,n). */
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdio.h>
#include <string.h>

static void swap(int *x, int *y) { int t = *x; *x = *y; *y = t; }
/* Strict comparisons preserve the order of equal keys. */
static void bubble_sort(int a[], size_t n)
{
    for (size_t end = n; end > 1; --end) {
        bool swapped = false;
        for (size_t j = 1; j < end; ++j) {
            if (a[j - 1] > a[j]) {
                swap(&a[j - 1], &a[j]); swapped = true;
            }
        }
        if (!swapped) return;
    }
}
/* Standard swapping selection sort is not stable. */
static void selection_sort(int a[], size_t n)
{
    for (size_t i = 0; i < n; ++i) {
        size_t smallest = i;
        for (size_t j = i + 1; j < n; ++j)
            if (a[j] < a[smallest]) smallest = j;
        if (smallest != i) swap(&a[i], &a[smallest]);
    }
}
/* Halving gaps: constant auxiliary space, quadratic worst-case time. */
static void shell_sort(int a[], size_t n)
{
    for (size_t gap = n / 2; gap > 0; gap /= 2) {
        for (size_t i = gap; i < n; ++i) {
            int key = a[i]; size_t j = i;
            while (j >= gap && a[j - gap] > key) {
                a[j] = a[j - gap]; j -= gap;
            }
            a[j] = key;
        }
    }
}
static void insertion_sort(int a[], size_t n)
{
    for (size_t i = 1; i < n; ++i) {
        int key = a[i];
        size_t j = i;
        while (j > 0 && a[j - 1] > key) {
            a[j] = a[j - 1];
            --j;
        }
        a[j] = key;
    }
}
/* Caller supplies a temporary array of at least n integers. */
static void merge_sort(int a[], int temp[], size_t n)
{
    if (n < 2) return;
    size_t mid = n / 2;
    merge_sort(a, temp, mid);
    merge_sort(a + mid, temp + mid, n - mid);
    size_t i = 0, j = mid, k = 0;
    while (i < mid && j < n)
        temp[k++] = a[i] <= a[j] ? a[i++] : a[j++];
    while (i < mid) temp[k++] = a[i++];
    while (j < n) temp[k++] = a[j++];
    for (k = 0; k < n; ++k) a[k] = temp[k];
}
/* Lomuto partition. Last element pivot: sorted/equal inputs give O(n^2). */
static void quick_sort(int a[], size_t n)
{
    if (n < 2) return;
    int pivot = a[n - 1];
    size_t p = 0;
    for (size_t j = 0; j + 1 < n; ++j)
        if (a[j] < pivot) swap(&a[p++], &a[j]);
    swap(&a[p], &a[n - 1]);
    quick_sort(a, p);
    quick_sort(a + p + 1, n - p - 1);
}
static void check(const int input[], size_t n)
{
    int a[16], b[16], c[16], d[16], e[16], f[16], temp[16];
    assert(n <= 16);
    memcpy(a, input, n * sizeof *a);
    memcpy(b, input, n * sizeof *b);
    memcpy(c, input, n * sizeof *c);
    memcpy(d, input, n * sizeof *d);
    memcpy(e, input, n * sizeof *e);
    memcpy(f, input, n * sizeof *f);
    insertion_sort(a, n); merge_sort(b, temp, n); quick_sort(c, n);
    bubble_sort(d, n); selection_sort(e, n); shell_sort(f, n);
    for (size_t i = 0; i < n; ++i) {
        assert(a[i] == b[i] && b[i] == c[i]);
        assert(c[i] == d[i] && d[i] == e[i] && e[i] == f[i]);
        assert(i == 0 || a[i - 1] <= a[i]);
    }
}
int main(void)
{
    int a[] = {5, 2, 4, 6, 1, 3};
    int duplicate[] = {3, -1, 3, 0, -1, 8};
    int ordered[] = {1, 2, 3, 4, 5};
    int reverse[] = {5, 4, 3, 2, 1};
    int equal[] = {7, 7, 7, 7};
    check(a, 6); check(duplicate, 6); check(ordered, 5);
    check(reverse, 5); check(equal, 4); check(a, 1); check(a, 0);
    /* Exhaust all ternary arrays of lengths 0..7: 3,280 inputs. */
    int generated[7];
    size_t combinations = 1;
    for (size_t length = 0; length <= 7; ++length) {
        for (size_t pattern = 0; pattern < combinations; ++pattern) {
            size_t digits = pattern;
            for (size_t i = 0; i < length; ++i) {
                generated[i] = (int)(digits % 3) - 1; digits /= 3;
            }
            check(generated, length);
        }
        combinations *= 3;
    }
    insertion_sort(a, 6);
    printf("Sorted:");
    for (size_t i = 0; i < 6; ++i) printf(" %d", a[i]);
    putchar('\n');
    puts("sorting tests passed");
    return 0;
}