#include <iostream>
#include <cassert>
#include <cstdlib>
#include <algorithm>
#include <sys/time.h>
using namespace std;
class TimeKeeper {
private:
static timeval b,e;
public:
static void start() {
gettimeofday(&b,NULL);
}
static void stop() {
gettimeofday(&e,NULL);
}
static double getTime() {
timeval temp;
timersub(&e, &b, &temp);
return temp.tv_sec * 1000000.0 + temp.tv_usec;
}
};
timeval TimeKeeper::b,TimeKeeper::e;
class Int {
public:
Int (int i = 0) : i(i) {}
Int (const Int &t) : i(t.i) { ++assign_count; }
Int &operator =(const Int &t) {
i = t.i;
++assign_count;
return *this;
}
bool operator <(const Int &t) const {
++comparision_count;
return i < t.i;
}
void swap(Int &t) {
++swap_count;
const int tmp = i;
i = t.i;
t.i = tmp;
}
static void reset() {
comparision_count = swap_count = assign_count = 0;
}
int i;
static int comparision_count;
static int swap_count;
static int assign_count;
};
namespace std {
template<>
void swap<Int>(Int &a, Int &b) {
a.swap(b);
}
}
int Int::comparision_count = 0;
int Int::swap_count = 0;
int Int::assign_count = 0;
void verify(Int *a, int n) {
for(int i = 1; i < n; ++i) {
assert(a[i-1].i <= a[i].i);
if( a[i-1].i > a[i].i ) cout << "Bad sorting" << endl;
}
}
void IBubble_sort(Int *arr, int n) {
for(int i = n; i > 1; ) {
int maxIndexSorted = 0;
for(int j = 1; j < i; ++j) {
if(arr[j] < arr[j-1]) {
maxIndexSorted = j;
arr[j].swap(arr[j-1]);
}
}
i = maxIndexSorted;
}
}
#define PARENT_OF(X) ((X-1)/2)
#define LCHILDOF(X) (X*2+1)
#define RCHILDOF(X) (X*2+2)
void insert_in_maxheap(Int *a, int i) {
while( i && a[PARENT_OF(i)] < a[i] ) {
a[i].swap(a[PARENT_OF(i)]);
i = PARENT_OF(i);
}
}
void rebalance_maxheap(Int *arr, int maxsize) {
int cur = 0;
while(cur < maxsize) {
int lc = LCHILDOF(cur), rc = RCHILDOF(cur);
if(lc + 1 >= maxsize) break;
int mc = (rc + 1 == maxsize) ? lc :
(arr[lc] < arr[rc]) ? rc : lc ;
if(arr[mc] < arr[cur]) break; // if(arr[mc] <= arr[cur]) break;
arr[cur].swap(arr[mc]);
cur = mc;
}
}
void heap_sort(Int *arr, int n) {
for(int i = 0; i < n; ++i) insert_in_maxheap(arr, i);
for(int i = n - 1; i > 0; --i) {
arr[i].swap(arr[0]);
rebalance_maxheap(arr, i + 1);
}
}
#if 1
# if 1
int next_shell_k(int s) {
switch(s) {
# define GEN(X) return X; case (X-1):
case 1749:
GEN(701);
GEN(301);
GEN(132);
GEN(57);
GEN(23);
GEN(10);
GEN(4);
GEN(1);
return -1;
}
# undef GEN
# define GEN(X) if(s > X) return X;
// http://sun.aei.polsl.pl/~mciura/publikacje/shellsort.pdf (P.114)
//GEN(1750);
GEN(701);
GEN(301);
GEN(132);
GEN(57);
GEN(23);
GEN(10);
GEN(4);
return 1;
# undef GEN
}
# else
int next_shell_k(int s) {
if(0 == s) return -1;
int c = s;
while(0 == (c % 6) ) c /= 6;
while(0 == (c % 3) ) c /= 3;
while(0 == (c % 2) ) c /= 2;
// using tail recursion
return (1 == c) ? s : next_shell_k(s-1);
}
# endif
void shell_sort(Int *a, int size) {
for (int k = next_shell_k( size / 2); k > 0; k = next_shell_k(k-1) ) {
for(int i = k; i < size; i++) {
for(int j = i - k; j >= 0; j -= k) {
if (a[j + k] < a[j]) a[j].swap(a[j+k]);
else break;
}
}
}
}
#else
void shell_sort(Int *a, int size) {
for (int k = size / 2; k > 0; k = k / 2 - 1) {
// Can perform better if we use k from a pre-calculated array
// where each element in array is reverse sorted of form
// pow(2,p) * pow(3,q) for some integer p and q
for(int i = k; i < size; i++) {
for(int j = i - k; j >= 0; j -= k) {
if (a[j + k] < a[j]) a[j].swap(a[j+k]);
else break;
}
}
}
}
#endif
void comb_sort(Int *a, int size) {
int gap = size;
bool swapped = false;
while ((gap > 1) || swapped) {
if (gap > 1) gap = int(gap/1.247330950103979);
swapped = false;
for (int i = 0; gap + i < size; i++)
if (a[i + gap] < a[i]) a[i + gap].swap(a[i]),swapped = true;
}
}
int quick(Int &pivot, Int *beg, Int *end) {
Int *start = --beg; // &pivot
while(beg < end) {
while(*++beg < pivot) if(beg == end) return (beg -start);
(beg--)->swap(*end);
while(pivot < *end) if(--end == beg) return (beg -start);
(++beg)->swap(*end);
}
return (beg -start);
}
void quick_sort(Int *a, int size) {
switch(size) {
case 0:
case 1:
return;
case 2:
if(a[1] < a[0]) a[1].swap(a[0]);
return;
case 3:
if(a[2] < a[1]) {
if(a[1] < a[0]) a[0].swap(a[2]); // reverse sorted
else {
a[1].swap(a[2]);
quick_sort(a, 2);
}
} else if(a[1] < a[0]) {
a[1].swap(a[0]);
quick_sort(a+1, 2);
}
return;
}
Int &pivot = a[0];
const int loc = quick(pivot, a+1, a+size-1);
a[0].swap(a[loc]);
quick_sort(a, loc);
quick_sort(a+loc+1, size - loc-1);
}
void selection_sort(Int *a, int size) {
if(size < 4) {
quick_sort(a, size);
return;
}
Int *const end = a + size;
size -= 3; // Leave last 3 element unsorted, we'll sort them using quick
for(int i = 0; i < size; ++i) {
int min_index = min_element(a + i, end) - a;
if(min_index != i) a[i].swap(a[min_index]);
}
quick_sort(a+size, 3);
}
void print_result(const char *sorting_type) {
cout << "=== " << sorting_type << " ===" << endl;
cout << " - Comparisions : " << Int::comparision_count << endl;
cout << " - Swaps : " << Int::swap_count << endl;
cout << " - Assignations : " << Int::assign_count << endl;
cout << " - Time : " << TimeKeeper::getTime() << " microsecond" << endl;
cout << endl;
}
void perform_inbuilt(Int *arr, int nsize) {
TimeKeeper::start();
sort(arr, arr+nsize);
TimeKeeper::stop();
verify(arr, nsize);
print_result("Inbuilt stl sort");
}
void perform_heap(Int *arr, int nsize) {
TimeKeeper::start();
heap_sort(arr, nsize);
TimeKeeper::stop();
verify(arr, nsize);
print_result("Heap sort");
}
void perform_improved_bubble(Int *arr, int nsize) {
TimeKeeper::start();
IBubble_sort(arr, nsize);
TimeKeeper::stop();
verify(arr, nsize);
print_result("Improved bubble sort");
}
void perform_shell(Int *arr, int nsize) {
TimeKeeper::start();
shell_sort(arr, nsize);
TimeKeeper::stop();
verify(arr, nsize);
print_result("Shell sort");
}
void perform_comb(Int *arr, int nsize) {
TimeKeeper::start();
comb_sort(arr, nsize);
TimeKeeper::stop();
verify(arr, nsize);
print_result("Comb sort");
}
void perform_quick(Int *arr, int nsize) {
TimeKeeper::start();
quick_sort(arr, nsize);
TimeKeeper::stop();
verify(arr, nsize);
print_result("Quick sort");
}
void perform_selection(Int *arr, int nsize) {
TimeKeeper::start();
selection_sort(arr, nsize);
TimeKeeper::stop();
verify(arr, nsize);
print_result("Selection sort");
}
void perform_all(Int *arr, Int *arr_copy, int nsize) {
std::copy(arr, arr+nsize, arr_copy);
Int::reset();
perform_inbuilt(arr_copy, nsize);
std::copy(arr, arr+nsize, arr_copy);
Int::reset();
perform_shell(arr_copy, nsize);
std::copy(arr, arr+nsize, arr_copy);
Int::reset();
perform_quick(arr_copy, nsize);
std::copy(arr, arr+nsize, arr_copy);
Int::reset();
perform_comb(arr_copy, nsize);
std::copy(arr, arr+nsize, arr_copy);
Int::reset();
perform_heap(arr_copy, nsize);
std::copy(arr, arr+nsize, arr_copy);
Int::reset();
perform_improved_bubble(arr_copy, nsize);
std::copy(arr, arr+nsize, arr_copy);
Int::reset();
perform_selection(arr_copy, nsize);
}
void print_line() {
std::cout << "----------------------------------------------------------------";
std::cout << std::endl;
std::cout << std::endl;
}
int main() {
const int nsize = 500;
Int arr[nsize] = {0};
srand(0);
for(int i = 0; i < nsize; ++i) arr[i] = rand() % 100000;
Int arr_copy[nsize];
cout << "Size of sample data = " << nsize << endl << endl;
// random_shuffle(arr, arr+nsize);
cout << "== Random data set ==" << endl << endl;
perform_all(arr, arr_copy, nsize);
print_line();
std::sort(arr, arr + nsize);
cout << "== Sorted data set ==" << endl << endl;
perform_all(arr, arr_copy, nsize);
print_line();
std::reverse(arr, arr + nsize);
cout << "== Reverse sorted data set ==" << endl << endl;
perform_all(arr, arr_copy, nsize);
print_line();
std::reverse(arr, arr + nsize);
arr[0].swap(arr[nsize-1]);
if(nsize > 10) arr[9].swap(arr[10]);
if(nsize > 50) arr[25].swap(arr[50]);
if(nsize > 100) arr[99].swap(arr[35]);
if(nsize > 1000) arr[299].swap(arr[350]);
cout << "== Almost sorted data set ==" << endl << endl;
perform_all(arr, arr_copy, nsize);
return 0;
}