Insertion sort in C++
Sort an array one item at a time. Take the next item and move it left until the item before it is not larger.
- File
insertion_sort.hpp, 26 lines- Level
- Native tests
- pass in this build
- Toolchain
- C++23, GCC 15 or Clang 21, with ASan and UBSan
- Test framework
- assert
- Run the tests
c++ -std=c++23 -Wall -Wextra -Wpedantic -Werror -fsanitize=address,undefined test_<name>.cpp && ./a.out
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
#pragma once
#include <cstddef>
#include <span>
#include <utility>
namespace algo {
// insertion_sort sorts a in place, in non-decreasing order. The sort is stable.
template <typename T>
void insertion_sort(std::span<T> a) {
for (std::size_t i = 1; i < a.size(); i++) { // @line L1
T key = std::move(a[i]); // @line L2
std::size_t j = i; // @line L3: j is one more than in the pseudocode
while (j > 0 && key < a[j - 1]) { // @line L4
a[j] = std::move(a[j - 1]); // @line L5
j--; // @line L6
}
a[j] = std::move(key); // @line L7
}
}
} // namespace algo
test_insertion_sort.cpp 32 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <string>
#include <vector>
#include "insertion_sort.hpp"
int main() {
std::vector<int> a{5, 2, 4, 6, 1, 3};
algo::insertion_sort(std::span<int>(a));
assert((a == std::vector<int>{1, 2, 3, 4, 5, 6}));
std::vector<std::string> w{"pear", "fig", "apple"};
algo::insertion_sort(std::span<std::string>(w));
assert((w == std::vector<std::string>{"apple", "fig", "pear"}));
std::mt19937 rng(2150);
for (int t = 0; t < 500; t++) {
std::vector<int> b(rng() % 41);
for (auto& v : b) v = static_cast<int>(rng() % 101) - 50;
auto want = b;
algo::insertion_sort(std::span<int>(b));
std::ranges::sort(want);
assert(b == want);
}
std::cout << "ok\n";
}
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work