[ create a new paste ] login | about

Link: http://codepad.org/zHBAG6vZ    [ raw code | output | fork | 1 comment ]

mohit_at_codepad - C++, pasted on May 24:
#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;
}


Output:
Size of sample data = 500

== Random data set ==

=== Inbuilt stl sort ===
 - Comparisions : 5289
 - Swaps        : 658
 - Assignations : 2947
 - Time         : 278 microsecond

=== Shell sort ===
 - Comparisions : 5661
 - Swaps        : 3103
 - Assignations : 0
 - Time         : 219 microsecond

=== Quick sort ===
 - Comparisions : 5746
 - Swaps        : 1836
 - Assignations : 0
 - Time         : 189 microsecond

=== Comb sort ===
 - Comparisions : 10034
 - Swaps        : 1891
 - Assignations : 0
 - Time         : 152 microsecond

=== Heap sort ===
 - Comparisions : 7565
 - Swaps        : 4243
 - Assignations : 0
 - Time         : 160 microsecond

=== Improved bubble sort ===
 - Comparisions : 124101
 - Swaps        : 65809
 - Assignations : 0
 - Time         : 723 microsecond

=== Selection sort ===
 - Comparisions : 124750
 - Swaps        : 491
 - Assignations : 0
 - Time         : 369 microsecond

----------------------------------------------------------------

== Sorted data set ==

=== Inbuilt stl sort ===
 - Comparisions : 3107
 - Swaps        : 0
 - Assignations : 1559
 - Time         : 107 microsecond

=== Shell sort ===
 - Comparisions : 2773
 - Swaps        : 0
 - Assignations : 0
 - Time         : 166 microsecond

=== Quick sort ===
 - Comparisions : 124998
 - Swaps        : 747
 - Assignations : 0
 - Time         : 742 microsecond

=== Comb sort ===
 - Comparisions : 9535
 - Swaps        : 0
 - Assignations : 0
 - Time         : 119 microsecond

=== Heap sort ===
 - Comparisions : 9745
 - Swaps        : 6996
 - Assignations : 0
 - Time         : 148 microsecond

=== Improved bubble sort ===
 - Comparisions : 499
 - Swaps        : 0
 - Assignations : 0
 - Time         : 100 microsecond

=== Selection sort ===
 - Comparisions : 124749
 - Swaps        : 0
 - Assignations : 0
 - Time         : 326 microsecond

----------------------------------------------------------------

== Reverse sorted data set ==

=== Inbuilt stl sort ===
 - Comparisions : 3109
 - Swaps        : 250
 - Assignations : 1559
 - Time         : 109 microsecond

=== Shell sort ===
 - Comparisions : 4416
 - Swaps        : 2094
 - Assignations : 0
 - Time         : 190 microsecond

=== Quick sort ===
 - Comparisions : 124998
 - Swaps        : 746
 - Assignations : 0
 - Time         : 449 microsecond

=== Comb sort ===
 - Comparisions : 10034
 - Swaps        : 708
 - Assignations : 0
 - Time         : 127 microsecond

=== Heap sort ===
 - Comparisions : 7010
 - Swaps        : 3676
 - Assignations : 0
 - Time         : 146 microsecond

=== Improved bubble sort ===
 - Comparisions : 124750
 - Swaps        : 124750
 - Assignations : 0
 - Time         : 411 microsecond

=== Selection sort ===
 - Comparisions : 124749
 - Swaps        : 250
 - Assignations : 0
 - Time         : 330 microsecond

----------------------------------------------------------------

== Almost sorted data set ==

=== Inbuilt stl sort ===
 - Comparisions : 3109
 - Swaps        : 3
 - Assignations : 1560
 - Time         : 107 microsecond

=== Shell sort ===
 - Comparisions : 3089
 - Swaps        : 324
 - Assignations : 0
 - Time         : 174 microsecond

=== Quick sort ===
 - Comparisions : 95962
 - Swaps        : 738
 - Assignations : 0
 - Time         : 385 microsecond

=== Comb sort ===
 - Comparisions : 10034
 - Swaps        : 618
 - Assignations : 0
 - Time         : 128 microsecond

=== Heap sort ===
 - Comparisions : 10179
 - Swaps        : 6902
 - Assignations : 0
 - Time         : 189 microsecond

=== Improved bubble sort ===
 - Comparisions : 124750
 - Swaps        : 1172
 - Assignations : 0
 - Time         : 430 microsecond

=== Selection sort ===
 - Comparisions : 124749
 - Swaps        : 4
 - Assignations : 0
 - Time         : 329 microsecond



Create a new paste based on this one


Comments:
posted by mohit_at_codepad on Jun 17
I received a comment in email:
Q: I am using your code framework to add and compare my sorting implementation. Is it safe to use >, >=, <= operator if I am looking for comparison counts.

Here is my answer:
A: No. If your implementation use above operators, the result may be incorrect. Three possible workarounds are:
1. Limit your implementation to use only Int::operator<.
2. Implement Int::operator>, Int::operator>= and Int::operator<=.
3. Implement Int::operator== and use namespace rel_ops.
reply