Insertion Sort

# Insertion Sort

Zerethon Official Sample `insertion-sort`, version 1.2.0, C++ (GCC 14).

- `insertion_sort.cpp` / `insertion_sort.hpp` — the algorithm (the same steps as this sample's C code)
- `main.cpp` — entry file: a short demonstration
- `test_insertion_sort.cpp` — checks; set it as the entry file to run them (or Run ▾ → Run tests)

Run compiles the entry file together with every other `.cpp` 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/insertion-sort-visualizer

// Insertion Sort (Zerethon Official Sample: insertion-sort 1.2.0).
#include "insertion_sort.hpp"
#include <utility>

void insertion_sort(std::vector<int> &a) {
    for (size_t i = 1; i < a.size(); i++) {
        const int key = a[i];
        int j = static_cast<int>(i) - 1;
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }
        a[j + 1] = key;
    }
}

// Insertion Sort (Zerethon Official Sample: insertion-sort 1.2.0).
#pragma once
#include <vector>

void insertion_sort(std::vector<int> &a);

#include <algorithm>
#include <iostream>
#include <vector>
#include "insertion_sort.hpp"

static void print(const char *label, const std::vector<int> &a) {
    std::cout << label << '[';
    for (size_t i = 0; i < a.size(); i++) std::cout << (i ? ", " : "") << a[i];
    std::cout << "]\n";
}

int main() {
    const std::vector<int> numbers = {38, 27, 43, 3, 9, 82, 10, 27};
    print("Before: ", numbers);
    std::vector<int> result = numbers;
    insertion_sort(result);
    print("After:  ", result);
    std::vector<int> expected = numbers;
    std::sort(expected.begin(), expected.end());
    std::cout << "Same as std::sort: " << std::boolalpha << (result == expected) << '\n';
}

// Checks for insertion_sort. To run them, set this file as the entry file
// (the ▶ button next to it in Files) and press Run.
#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
#include "insertion_sort.hpp"

// Deterministic pseudo-random integers in [-50, 49] (the same as the other languages' checks).
static std::vector<int> numbers(long long seed, int count) {
    std::vector<int> out;
    for (int i = 0; i < count; i++) {
        seed = (seed * 1103515245LL + 12345LL) % 2147483648LL;
        out.push_back(static_cast<int>(seed % 100) - 50);
    }
    return out;
}

int main() {
    std::vector<std::vector<int>> cases = {{}, {1}, {2, 1}, {1, 2, 3}, {3, 2, 1}, {5, 1, 5, 1, 5}, {-3, 0, -1, 2}};
    for (const auto &[seed, size] : std::vector<std::pair<int, int>>{{1, 10}, {2, 50}, {3, 200}}) cases.push_back(numbers(seed, size));

    for (size_t i = 0; i < cases.size(); i++) {
        std::vector<int> result = cases[i], expected = cases[i];
        insertion_sort(result);
        std::sort(expected.begin(), expected.end());
        if (result != expected) {
            std::cerr << "insertion_sort: wrong result for case " << i + 1 << " (length " << cases[i].size() << ")\n";
            return 1;
        }
    }
    std::cout << "All " << cases.size() << " checks passed." << std::endl;
}