#include <algorithm>
#include <cassert>
#include <climits>
#include <functional>
#include <iomanip>
#include <iostream>
#include <iterator>
#include <random>
#include <stdexcept>
#include <type_traits>
#include <string>
#include <cstdlib>
#include <ctime>
#include <vector>
template<class bidi_iterator, class predicate>
void quick_sort(const bidi_iterator first, const bidi_iterator last, const predicate& pred) {
using std::swap;
using namespace std::placeholders;
if (first == last) //0
return;
bidi_iterator next = std::next(first);
if (next == last) // 1
return;
if (std::next(next) == last) { // 2
if (pred(*next, *first))
swap(*first, *next);
return;
}
//3+
bidi_iterator mid = std::partition(next, last, std::bind(pred, _1, std::cref(*first)));
bidi_iterator prev = std::prev(mid);
swap(*first, *prev);
if (next!=mid && next!=prev) //2+ on left
quick_sort(first, prev, pred);
if (mid!=last && mid!=std::prev(last)) //2+ on right
quick_sort(mid, last, pred);
assert(std::is_sorted(first, last, pred));
}
template<class bidi_iterator>
void quick_sort(const bidi_iterator first, const bidi_iterator last) {
typedef typename std::iterator_traits<bidi_iterator>::value_type value_type;
return quick_sort(first, last, std::less<value_type>());
}
template<class bidi_iterator, class predicate>
void inplace_sort(const bidi_iterator first, const bidi_iterator last, const predicate& pred) {
using std::swap;
using namespace std::placeholders;
bidi_iterator beginchunk = first;
bidi_iterator unorganized = first;
bidi_iterator endchunk = first;
//while there's more to do
while(beginchunk != last) {
//if we haven't yet organized any data
if (beginchunk == unorganized) {
//then begin points at our new pivot
bidi_iterator n(std::next(beginchunk));
if (n == last) return;
//partition everything from here to the end of the data
//mark the right side as completely unorganized
unorganized = std::partition(n, last, std::bind(pred, _1, std::cref(*beginchunk)));
//and now that the left side is partially organized
//as a pivot followed by all unsorted elements less than the pivot
//if there's more then one on the left, we "recurse" down the left.
if (unorganized != n)
endchunk = unorganized;
//otherwise, "recurse" down the right
else {
beginchunk = unorganized;
continue;
}
}
//if we don't yet know where the end of those unsorted elements are, we'll have to find them
if (beginchunk == endchunk) {
++endchunk;
//if some are already sorted, skip them
while(endchunk!=unorganized && pred(*beginchunk, *endchunk)) {
++beginchunk;
++endchunk;
}
//if sorted all the way to the unorganized, jump up to that bit
if (endchunk == unorganized) {
beginchunk = unorganized;
continue;
}
//if we got this far, that means we found a pivot followed by one less than the pivot
++endchunk;
//data was already organized as a pivot followed by the unsorted elements less than that pivot
//so we find the next element that's greater than the pivot
while(endchunk!=unorganized && pred(*endchunk, *beginchunk))
++endchunk;
}
//beginchunk points at the old pivot
//so n points at the first element in this chunk, which will be our new pivot
bidi_iterator n(std::next(beginchunk));
if (n != endchunk) {
//so we'll partition the data after the new pivot
bidi_iterator nn(std::next(n));
//if there's more than two elements in the chunk
if (nn != endchunk) {
//then we partition!
bidi_iterator midchunk = std::partition(nn, endchunk, std::bind(pred, _1, std::cref(*n)));
//here's the tricky part:
//this chunk was the old pivot followed by the unsorted elements less than it.
//we have to move the old pivot to between the two paritions we just now made
bidi_iterator prev(std::prev(midchunk));
swap(*beginchunk, *prev);
//and move the new pivot to the beginning of the first chunk
//which devides this into two chunks. Those less than the new pivot, and those less than the new
//which are preceeded by the new pivot and the old pivot respectively
//this allows us to detect the boundaries of both chunks
if (n != prev) {
swap(*beginchunk, *n);
//finally, we'll "recurse" on the left chunk
endchunk = prev;
} else {
//unless there was no elements less than the new pivot
//then we "recuse" down the right insead
beginchunk = n;
}
//oh, if there were only two elements in the chunk, then we just swap them
} else {
swap(*beginchunk, *n);
//and we don't know what's to the right, we'll discover that
//at the beginning of the next iteration;
beginchunk = nn;
endchunk = beginchunk;
}
} else {
++beginchunk;
}
}
}
template<class bidi_iterator>
void inplace_sort(bidi_iterator begin, bidi_iterator end) {
typedef typename std::iterator_traits<bidi_iterator>::value_type value_type;
return inplace_sort(begin, end, std::less<value_type>());
}
//tracer class used to track comparisons and swaps
//other numbers aren't used in this test
template <typename T>
struct tracer {
T value;
tracer() :value() {++default_construct_count;}
tracer(const tracer& rhs) :value(rhs.value) {++copy_construct_count;}
//template<class U> tracer(std::enable_if<std::is_convertible<U, T>::value, const U&>::type v) :value(v) {++conversion_construct_count;}
template<class U> tracer(const U& v) :value(v) {++conversion_construct_count;}
~tracer() {++destructor_count;}
tracer& operator=(const tracer& rhs) { value = rhs.value; ++copy_assign_count; return *this; }
//template<class U> tracer<T>& operator=(std::enable_if<std::is_convertible<U, T>::value, const U&>::type v) { value = v; ++conversion_assign_count; return *this; }
template<class U> tracer<T>& operator=(const U& v) { value = v; ++conversion_assign_count; return *this; }
static unsigned long long default_construct_count;
static unsigned long long copy_construct_count;
static unsigned long long conversion_construct_count;
static unsigned long long compare_count;
static unsigned long long swap_count;
static unsigned long long copy_assign_count;
static unsigned long long conversion_assign_count;
static unsigned long long destructor_count;
};
template<class T>
void reset_counts(tracer<T>) {
tracer<T>::default_construct_count = 0;
tracer<T>::copy_construct_count = 0;
tracer<T>::conversion_construct_count = 0;
tracer<T>::compare_count = 0;
tracer<T>::swap_count = 0;
tracer<T>::copy_assign_count = 0;
tracer<T>::conversion_assign_count = 0;
tracer<T>::destructor_count = 0;
}
template<class T>
void show_counts(tracer<T>) {
std::cout << std::setw(10) << tracer<T>::compare_count << ' ';
std::cout << std::setw(10) << tracer<T>::swap_count << ' ';
}
template <typename T>
bool operator<(const tracer<T>& lhs, const tracer<T>& rhs)
{ ++tracer<T>::compare_count;return std::less<T>()(lhs.value,rhs.value);}
template <typename T>
void swap(tracer<T>& lhs, tracer<T>& rhs)
{using std::swap;swap(lhs.value, rhs.value);++tracer<T>::swap_count;}
template <typename T>
std::ostream& operator<<(std::ostream& stream, const tracer<T>& obj)
{ return stream << obj.value;}
template <typename T> unsigned long long tracer<T>::default_construct_count = 0;
template <typename T> unsigned long long tracer<T>::copy_construct_count = 0;
template <typename T> unsigned long long tracer<T>::conversion_construct_count = 0;
template <typename T> unsigned long long tracer<T>::compare_count = 0;
template <typename T> unsigned long long tracer<T>::swap_count = 0;
template <typename T> unsigned long long tracer<T>::copy_assign_count = 0;
template <typename T> unsigned long long tracer<T>::conversion_assign_count = 0;
template <typename T> unsigned long long tracer<T>::destructor_count = 0;
void reset_counts(int) {}
void reset_counts(std::string) {}
void show_counts(int) {
std::cout << std::setw(10) << '?' << ' ';
std::cout << std::setw(10) << '?' << ' ';
}
void show_counts(std::string) {
std::cout << std::setw(10) << '?' << ' ';
std::cout << std::setw(10) << '?' << ' ';
}
void hardcoded_tests() {
std::cout << "Beginning accuracy tests\n";
std::vector<int> t;
inplace_sort(t.begin(), t.end());
bool pass = std::is_sorted(t.begin(), t.end());
assert(pass);
//for all lengths of data from 1 to 7 inclusive
for(unsigned len=1; pass && len<8; ++len) {
std::vector<int> data(len, 0);
unsigned max = 1<<(len-1);
//for each pattern of increases or not-increases
//because {1,3,3} and {1,2,2} are effectively the same test
for(unsigned bits=0; pass && bits<max; ++bits) {
for(unsigned i=0; i<len-1; ++i) {
int v = (bits & (1<<i)) >> i;
data[i+1] = data[i] + v;
}
//test all permutations of that pattern
do {
t = data;
inplace_sort(t.begin(), t.end());
pass = std::is_sorted(t.begin(), t.end());
assert(pass);
} while(pass && std::next_permutation(data.begin(), data.end()));
}
}
if (pass) std::cout << "Passed all accuracy tests" << std::endl;
else {
std::cout << "Failed on {";
for(unsigned i=0; i<t.size(); ++i) {
if (i!=0) std::cout << ' ';
std::cout << t[i];
}
std::cout << "}" << std::endl;
}
}
template<class type, class generator>
void timing_tests(generator& gen, const char* name_of_type ) {
std::cout << "Beginning timing tests with " << name_of_type << "\n";
std::cout << "name N comps swaps ticks\n";
const unsigned test_size=2097152;
//clock_t stop = clock() + CLOCKS_PER_SEC/4; //.25
//for(unsigned test_size=32; test_size<=INT_MAX && clock()<stop; test_size*=2)
{
clock_t sort_time=0;
std::vector<type> data(test_size);
for(unsigned i=0; i<data.size(); ++i)
data[i] = gen();
std::vector<type> data2;
std::cout << "quick " << std::setw(10) << test_size << ' ' << std::flush;
data2 = data;
quick_sort(data2.begin(), data2.end());
assert(std::is_sorted(data2.begin(), data2.end()));
data2 = data;
reset_counts(data[0]);
clock_t begin = clock();
quick_sort(data2.begin(), data2.end());
sort_time = clock()-begin;
show_counts(data[0]);
std::cout << std::setw(10) << sort_time << std::endl;
std::cout << "inplace " << std::setw(10) << test_size << ' ' << std::flush;
data2 = data;
inplace_sort(data2.begin(), data2.end());
assert(std::is_sorted(data2.begin(), data2.end()));
data2 = data;
reset_counts(data[0]);
begin = clock();
inplace_sort(data2.begin(), data2.end());
sort_time = clock()-begin;
show_counts(data[0]);
std::cout << std::setw(10) << sort_time << std::endl;
}
std::cout << "Finished timing tests\n";
}
struct randstring {
randstring(unsigned len, std::mt19937& generator)
:l(len), gen(&generator), dist(CHAR_MIN,CHAR_MAX) {}
std::string operator()() {
std::string r(l, '\0');
for(unsigned i=0; i<l; ++i)
r[i] = (char)dist(*gen);
return r;
}
unsigned l;
std::mt19937* gen;
std::uniform_int_distribution<int> dist;
};
int main() {
srand(time(NULL));
std::mt19937 gen(rand());
std::uniform_int_distribution<int> dist(INT_MIN, INT_MAX);
auto intrng = std::bind(dist, gen);
randstring strrng(17u, gen);
hardcoded_tests();
timing_tests<tracer<int>>(intrng, "tracer<int>");
timing_tests<int>(intrng, "int");
timing_tests<std::string>(strrng, "string");
return 0;
}