Heap Sort

# Heap Sort

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

- `heap_sort.c` / `heap_sort.h` — the algorithm, as shown in Zerethon Tools
- `main.c` — entry file: a short demonstration
- `test_heap_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/heap-sort-visualizer

/* Heap Sort (Zerethon Official Sample: heap-sort 1.1.0).
   The algorithm as shown in Zerethon Tools. */
#include "heap_sort.h"

void sift_down(int a[], int lo, int hi) {
    int root = lo;
    while (2 * root + 1 <= hi) {
        int child = 2 * root + 1;
        if (child + 1 <= hi && a[child] < a[child + 1]) child++;
        if (a[root] < a[child]) {
            int t = a[root]; a[root] = a[child]; a[child] = t;
            root = child;
        } else return;
    }
}
void heap_sort(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) sift_down(a, i, n - 1);
    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t;
        sift_down(a, 0, end - 1);
    }
}

/* Heap Sort (Zerethon Official Sample: heap-sort 1.1.0). */
#ifndef HEAP_SORT_H
#define HEAP_SORT_H

void sift_down(int a[], int lo, int hi);
void heap_sort(int a[], int n);

#endif

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "heap_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);
    heap_sort(result, n);
    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;
}

// Checks for heap_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 "heap_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]);
    heap_sort(result, n);
    qsort(expected, n, sizeof expected[0], compare);
    checks++;
    if (memcmp(result, expected, n * sizeof c[0]) != 0) {
        fprintf(stderr, "heap_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;
}