This is a follow-up question to Sorting algorithms - Bubble sort
Again, for practice purposes only, I took on an implementation of the well known insertion sort as a method to be used similarly to std::sort
.
As expected, the code lives inside a header file called insertion_sort.h:
#pragma once
#include <iterator>
#include <algorithm>
namespace sorting_algorithms {
template <typename BidirectionalIterator,
typename Comparator = std::less<>>
void insertion_sort(BidirectionalIterator begin, BidirectionalIterator end,
Comparator cmp = {}) {
if (std::distance(begin, end) < 2) {
return;
}
for (auto current_element = std::next(begin); current_element != end;
++current_element) {
for (auto i = std::prev(current_element), i_next = current_element;
i_next != begin; --i, --i_next) {
auto& i_val = *i;
auto& i_next_val = *i_next;
if (cmp(i_val, i_next_val)) {
break;
}
std::iter_swap(&i_val, &i_next_val);
}
}
}
}
I tried to follow most hints and suggestions I received for my previous question about bubble sort. I am aware of the fact that the algorithm can also be implemented in a way that only requires forward iterators, but I decided to require bidirectional iterators here for ease of implementation.
Again, I also provide you a main
file for simple compilation and testing purposes:
#include <random>
#include <vector>
#include <iostream>
#include <iomanip>
#include <chrono>
#include <algorithm>
#include "insertion_sort.h"
int main() {
unsigned seed =
std::chrono::system_clock::now().time_since_epoch().count();
std::default_random_engine engine(seed);
std::uniform_int_distribution<unsigned> distribution(0, 10000);
std::vector<unsigned> vec;
for (std::size_t i = 0; i < 100; ++i) {
unsigned num = distribution(engine) + 1;
std::cout << num << ' ';
vec.push_back(num);
}
std::cout << "\n\n";
sorting_algorithms::insertion_sort(vec.begin(), vec.end());
for (const auto& e : vec) {
std::cout << e << ' ';
}
std::cout << std::boolalpha;
std::cout << "\nSorted? " << std::is_sorted(vec.begin(), vec.end())
<< "\n\n";
sorting_algorithms::insertion_sort(vec.begin(), vec.end(),
[] (const auto& v0, const auto& v1) {
return v0 > v1;
});
for (unsigned e : vec) {
std::cout << e << ' ';
}
std::cout << "\nSorted (in reverse order)? "
<< std::is_sorted(vec.begin(), vec.end(),
[] (const auto& v0, const auto& v1) {
return v0 > v1;
}) << '\n';
}