Skip to content

Instantly share code, notes, and snippets.

@thealmarty
Created February 13, 2021 18:46
Show Gist options
  • Save thealmarty/f88189688e26db735a0aec83ad8e6ce3 to your computer and use it in GitHub Desktop.
Save thealmarty/f88189688e26db735a0aec83ad8e6ce3 to your computer and use it in GitHub Desktop.
Insertion sort in C++
#include <iostream>
#include <vector>
void insertion_sort(std::vector<int> & v) {
// invariant: the first i elements of v are sorted
for(size_t i = 1; i < v.size(); ++i) {
int value = v[i];
size_t j = i-1;
// invariant: elements of v from j+1 to i inclusive are sorted and >= value
for(; j >= 0 && v[j] > value; --j) {
v[j+1] = v[j];
}
v[j+1] = value;
}
}
void insertion_sort_no_copies(std::vector<int> & v) {
// invariant: the first i elements of v are sorted
for(size_t i = 1; i < v.size(); ++i) {
// invariant: elements of v from j+1 to i inclusive are sorted and >= value
for(size_t j = i-1; j >= 0 && v[j] > v[j+1]; --j) {
std::swap(v[j],v[j+1]);
}
}
}
int main() {
std::vector<int> v{6, 3, 5, 4, 2, 1};
insertion_sort_no_copies(v);
for(int const x : v) {
std::cout << x << std::endl;
}
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment