Quick Sort

# Quick Sort

Zerethon Official Sample `quick-sort`, version 1.1.0, C (GCC 14).

- `quick_sort.c` / `quick_sort.h` — the algorithm, as shown in Zerethon Tools
- `main.c` — entry file: a short demonstration
- `test_quick_sort.c` — checks; set it as the entry file to run them

Run compiles the entry file together with every other `.c` file except other programs
(files whose name starts with `main` or `test_`).

This project is your own copy. Changing it never changes the official sample.
See the algorithm animated: https://tools.zerethon.com/quick-sort-visualizer

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "quick_sort.h"

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

static int compare(const void *x, const void *y) {
    return (*(const int *) x > *(const int *) y) - (*(const int *) x < *(const int *) y);
}

int main(void) {
    int numbers[] = {38, 27, 43, 3, 9, 82, 10, 27};
    int n = sizeof numbers / sizeof numbers[0];
    int result[sizeof numbers / sizeof numbers[0]], expected[sizeof numbers / sizeof numbers[0]];

    print_array("Before: ", numbers, n);
    memcpy(result, numbers, sizeof numbers);
    quick_sort(result, 0, n - 1);
    print_array("After:  ", result, n);
    memcpy(expected, numbers, sizeof numbers);
    qsort(expected, n, sizeof expected[0], compare);
    printf("Same as qsort(): %s\n", memcmp(result, expected, sizeof result) == 0 ? "true" : "false");
    return 0;
}

/* Quick Sort (Zerethon Official Sample: quick-sort 1.1.0).
   The algorithm as shown in Zerethon Tools. */
#include "quick_sort.h"

void quick_sort(int a[], int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++) {
        if (a[j] < pivot) {
            int t = a[i]; a[i] = a[j]; a[j] = t;
            i++;
        }
    }
    int t = a[i]; a[i] = a[hi]; a[hi] = t;
    quick_sort(a, lo, i - 1);
    quick_sort(a, i + 1, hi);
}

/* Quick Sort (Zerethon Official Sample: quick-sort 1.1.0). */
#ifndef QUICK_SORT_H
#define QUICK_SORT_H

void quick_sort(int a[], int lo, int hi);

#endif

// Checks for quick_sort. To run them, set this file as the entry file
// (the ▶ button next to it in Files) and press Run.
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "quick_sort.h"

static int compare(const void *x, const void *y) {
    return (*(const int *) x > *(const int *) y) - (*(const int *) x < *(const int *) y);
}

/* Deterministic pseudo-random integers in [-50, 49] (the same as the Python checks). */
static void numbers(long long seed, int count, int *out) {
    for (int i = 0; i < count; i++) {
        seed = (seed * 1103515245LL + 12345LL) % 2147483648LL;
        out[i] = (int) (seed % 100) - 50;
    }
}

static int checks = 0;

static int check(const int *c, int n) {
    int result[200], expected[200];
    memcpy(result, c, n * sizeof c[0]);
    memcpy(expected, c, n * sizeof c[0]);
    quick_sort(result, 0, n - 1);
    qsort(expected, n, sizeof expected[0], compare);
    checks++;
    if (memcmp(result, expected, n * sizeof c[0]) != 0) {
        fprintf(stderr, "quick_sort: wrong result for case %d (length %d)\n", checks, n);
        return 0;
    }
    return 1;
}

int main(void) {
    int ok = 1;
    ok &= check((int[]) {0}, 0);
    ok &= check((int[]) {1}, 1);
    ok &= check((int[]) {2, 1}, 2);
    ok &= check((int[]) {1, 2, 3}, 3);
    ok &= check((int[]) {3, 2, 1}, 3);
    ok &= check((int[]) {5, 1, 5, 1, 5}, 5);
    ok &= check((int[]) {-3, 0, -1, 2}, 4);
    int random[200];
    numbers(1, 10, random);
    ok &= check(random, 10);
    numbers(2, 50, random);
    ok &= check(random, 50);
    numbers(3, 200, random);
    ok &= check(random, 200);

    if (!ok) return 1;
    printf("All %d checks passed.\n", checks);
    return 0;
}