My implementation of insertion, merge, and quick sort, with some utility testing functions. I just wanted to know how I can improve the efficiency and general cleanliness of my code.
(note: I know C++ has partition, but I want to do most of the implementation myself)
In particular, my main algorithms take iterators [first, last], but STL container's v.begin() and v.end() go 1 over the last element, so I have wrappers that call the main algorithm with first and end - 1.
How can I restructure this into the main algorithm (if that would be better)?
#include <iterator>
#include <vector>
using namespace std;
// Insert sort O(n^2) time O(1) space
template <typename Iterator>
void ins_sort(Iterator first, Iterator end) {
for (Iterator cur = first; cur < end; ++cur) {
auto key = *cur;
Iterator ins = cur - 1;
for (; first <= ins && key < *ins; --ins)
*(ins + 1) = *ins; // move 1 to right until correct position's found
*(ins + 1) = key;
}
}
// Merge sort O(nlogn) time O(n) space
template <typename Iterator>
void merge(Iterator first, Iterator middle, Iterator last) {
using T = typename iterator_traits<Iterator>::value_type;
vector<T> left(first, middle + 1);
vector<T> right(middle + 1, last + 1);
left.push_back(0xFFFFFFF); // sentinel
right.push_back(0xFFFFFFF);
for (int i = 0, j = 0, k = 0; k <= last - first; ++k) {
if (left[i] < right[j]) first[k] = left[i++];
else first[k] = right[j++];
}
}
template <typename Iterator>
void merge_helper(Iterator first, Iterator last) {
if (first < last) {
Iterator pivot = first + (last - first)/2; // half way point rounded down
merge_helper(first, pivot);
merge_helper(pivot + 1, last);
merge(first, pivot, last);
}
}
template <typename Iterator>
void mer_sort(Iterator first, Iterator end) {
merge_helper(first, end - 1);
}
// Quick sort O(nlogn) time O(n) space
template <typename Iterator>
void quick_sort(Iterator first, Iterator last) {
if (last - first > 0) {
auto pivot = *(first + (last - first) / 2);
Iterator left {first};
Iterator right {last};
while (left <= right) {
while (*left < pivot) ++left;
while (pivot < *right) --right;
if (left <= right) { swap(*left, *right); ++left; --right; }
}
quick_sort(first, right);
quick_sort(left, last);
}
}
template <typename Iterator>
void qck_sort(Iterator first, Iterator end) {
quick_sort(first, end - 1);
}
Testing code
#include <random>
#include <vector>
#include <iostream>
using namespace std;
class Rand_int {
public:
Rand_int(int low, int high) : distribution{low, high} {
}
int operator()() {
return distribution(engine);
}
private:
default_random_engine engine;
uniform_int_distribution<> distribution;
};
template <typename T>
void print(vector<T> v) {
for (auto x : v)
cout << x << ' ';
cout << '\n';
}
vector<int> randgen(int max, int num) {
static Rand_int die{0, max};
vector<int> res(num);
for (int i = 0; i < num; ++i)
res[i] = die();
return res;
}
