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; } 
