codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
#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; }
Private
[
?
]
Run code
Submit