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.c, 16 lines- Level
- Native tests
- pass in this build
- Toolchain
- C23, GCC 15 or Clang 21, with ASan and UBSan
- Test framework
- assert
- Run the tests
cc -std=c2x -Wall -Wextra -Wpedantic -Werror -fsanitize=address,undefined *.c && ./a.out
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
#include "insertion_sort.h"
void insertion_sort(int64_t *a, size_t n) {
for (size_t i = 1; i < n; i++) { // @line L1
int64_t key = a[i]; // @line L2
size_t j = i; // @line L3: j is one more than in the pseudocode, so it stays unsigned
while (j > 0 && a[j - 1] > key) { // @line L4
a[j] = a[j - 1]; // @line L5
j--; // @line L6
}
a[j] = key; // @line L7
}
}
insertion_sort.h 13 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
#ifndef INSERTION_SORT_H
#define INSERTION_SORT_H
#include <stddef.h>
#include <stdint.h>
// insertion_sort sorts a[0..n-1] in place, in non-decreasing order. The sort is stable.
void insertion_sort(int64_t *a, size_t n);
#endif
test_insertion_sort.c 34 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/insertion-sort/. The authors are listed in prov/3NS7RT.jsonl.
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "insertion_sort.h"
static int cmp(const void *p, const void *q) {
int64_t a = *(const int64_t *)p, b = *(const int64_t *)q;
return (a > b) - (a < b);
}
int main(void) {
int64_t a[] = {5, 2, 4, 6, 1, 3};
const int64_t want[] = {1, 2, 3, 4, 5, 6};
insertion_sort(a, 6);
assert(memcmp(a, want, sizeof a) == 0);
insertion_sort(NULL, 0);
srand(2150);
int64_t b[40], c[40];
for (int t = 0; t < 500; t++) {
size_t n = (size_t)(rand() % 41);
for (size_t i = 0; i < n; i++) b[i] = c[i] = rand() % 101 - 50;
insertion_sort(b, n);
qsort(c, n, sizeof c[0], cmp);
assert(n == 0 || memcmp(b, c, n * sizeof b[0]) == 0);
}
puts("ok");
return 0;
}
What the next level needs
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work