fork download
copy 
  1. #include <algorithm>
  2. #include <cassert>
  3. #include <functional>
  4. #include <iostream>
  5. #include <iterator>
  6. #include <map>
  7. #include <string>
  8. #include <type_traits>
  9. #include <vector>
  10.  
  11. void startClock() {}
  12. double getClock()
  13. {
  14.     return 0;
  15. };
  16.  
  17. // ------------ QUICK SORT ------------------
  18. template<typename T, typename key_compare>
  19. void quicksort( T first, T last, const size_t pivot_index, key_compare comp )
  20. {
  21.     T saved_first = first;
  22.     size_t N = last - first;
  23.     if (N > 1)
  24.     {
  25.         // create a temp new array, which contains all items less than pivot
  26.         // on left and greater on right. With pivot value in between.
  27.         // vector<typename decltype(*T)> temp(N);
  28.         typename std::iterator_traits<T>::pointer temp = (typename std::iterator_traits<T>::pointer) malloc(sizeof(T)*N);
  29.         size_t left_index = 0, right_index = N - 1 ;
  30.         typename std::iterator_traits<T>::value_type pivot_val = *(first + pivot_index);
  31.         for(; first < saved_first + pivot_index; first++)
  32.         {
  33.             if( !comp(*first, pivot_val) )
  34.             {
  35.                 temp[right_index--] = *first;
  36.             }
  37.             else
  38.             {
  39.                 temp[left_index++] = *first;
  40.             }
  41.         }
  42.         // skip the pivot value
  43.         // TODO: swap the pivot to end so we can have a single loop instead.
  44.         ++first;
  45.         // do the rest
  46.         for(; first < last; first++)
  47.         {
  48.             if( !comp(*first, pivot_val) )
  49.             {
  50.                 temp[right_index--] = *first;
  51.             }
  52.             else
  53.             {
  54.                 temp[left_index++] = *first;
  55.             }
  56.         }
  57.         if( right_index == left_index )
  58.         {
  59.             temp[left_index] = pivot_val;
  60.         }
  61.         else
  62.         {
  63.             temp[left_index+1] = pivot_val;
  64.         }
  65.         // recurse for left and right..
  66.         quicksort(temp, temp+left_index, left_index/2, comp);
  67.         quicksort(temp+left_index+1, temp+N, (N-right_index)/2, comp);
  68.  
  69.         // return a concat'd array..
  70.         for(size_t i = 0; i < N; i++)
  71.         {
  72.             *saved_first++ = temp[i];
  73.         }
  74.  
  75.         free(temp);
  76.     }
  77. }
  78. /*
  79. ** best, average, worst: n log n, n log n, n^2
  80. ** space: log n
  81. */
  82. template<typename T, typename key_compare >
  83. void quicksort( T first, T last, key_compare comp )
  84. {
  85.     size_t pivot_index = (last - first) / 2;
  86.     quicksort( first, last, pivot_index, comp);
  87. }
  88.  
  89. // ------------ QUICK with optimizations ------------------
  90. /*
  91. quicksort partition on range [first, last[ using predicate function as the comparator.
  92. "mid" is in-out param, function uses mid as mid, and updates it before returning it with
  93. current/new mid position after partitioning.
  94. */
  95. template<typename T, typename key_compare >
  96. void _partial_quicksort_partition( T first, T last, T& mid, key_compare comp )
  97. {
  98.     T savedFirst = first;
  99.     typedef typename std::iterator_traits<T>::value_type _val_type;
  100.     size_t N = last - first;
  101.     _val_type *temp = (_val_type *) malloc((N*sizeof(_val_type)));
  102.  
  103.     // move pivot to the end..
  104.     _val_type pivot_val = *mid;
  105.     std::swap(*mid, *(last - 1));
  106.     size_t left_index = 0, right_index = N - 1;
  107.  
  108.     for( ; first != last - 1; first++ )
  109.     {
  110.         if( !comp(*first, pivot_val) )
  111.         {
  112.             temp[right_index--] = *first;
  113.         }
  114.         else
  115.         {
  116.             temp[left_index++] = *first;
  117.         }
  118.     }
  119.  
  120.     assert( right_index == left_index );
  121.  
  122.     temp[left_index] = pivot_val;
  123.  
  124.     std::copy(temp, temp+N, savedFirst);
  125.     free(temp);
  126.     mid = savedFirst + left_index;
  127. }
  128.  
  129. template<typename T, typename key_compare >
  130. void _partial_quicksort( T first, T last, key_compare comp )
  131. {
  132.     size_t s = last - first;
  133.     // sort only if the list is smaller than our limit.. else it's too small for
  134.     // us to bother.. caller would take care of it using some other stupid algo..
  135.     if( 16 > s )
  136.     {
  137.         // only one call to insertion_sort(), after whole array is partially sorted
  138.         // using quicksort().
  139.         // insertion_sort(first, last, pred);
  140.         return ;
  141.     }
  142.  
  143.     // select pivot.. use median 3
  144.     T mid = median3(first, last - 1, s, comp);
  145.     // partition
  146.     _partial_quicksort_partition(first, last, mid, comp);
  147.     // recurse..
  148.     _partial_quicksort(first, mid, comp);
  149.     // tail recurse..
  150.     // TODO: tail recurse on longer partition..
  151.     _partial_quicksort(mid+1, last, comp);
  152. }
  153.  
  154. template<typename T, typename key_compare >
  155. void mixed_quicksort( T first, T last, key_compare pred )
  156. {
  157.     _partial_quicksort(first, last, pred );
  158.     insertion_sort(first, last, pred);
  159. }
  160.  
  161. // ------------ "in place" QUICK with optimizations ------------------
  162. /*
  163. in place quicksort partition on range [first, last[ using predicate function as the comparator.
  164. "mid" is in-out param, function uses mid as mid, and updates it before returning it with
  165. current/new mid position after partitioning.
  166. */
  167. template<typename T, typename key_compare >
  168. void _partial_inplace_quicksort_partition( T first, T last, T& mid, key_compare comp )
  169. {
  170.     typename std::iterator_traits<T>::value_type midVal = *mid;
  171.     // move pivot to end..
  172.     std::swap(*mid, *(last - 1));
  173.     mid = first;
  174.     // in-place quick sort:
  175.     for( ; first < last - 1; first++ )
  176.     {
  177.         if( comp(*first, midVal) )
  178.         {
  179.             std::swap(*first, *mid);
  180.             mid++;
  181.         }
  182.     }
  183.     // bring pivot to the mid..
  184.     std::swap(*mid, *(last - 1));
  185. }
  186.  
  187. // brings best median to middle and returns it..
  188. // works on array as [first, last] NOT [first, last[
  189. template<typename T, typename key_compare >
  190. T median3(T first, T last, size_t size, key_compare comp )
  191. {
  192.     T mid = first + size/2;
  193.     if (comp(*mid, *first))
  194.     {
  195.         std::swap(*mid, *first);
  196.     }
  197.     if (comp(*last, *mid))
  198.     {
  199.         std::swap(*last, *mid);
  200.     }
  201.     if (comp(*mid, *first))
  202.     {
  203.         std::swap(*mid, *first);
  204.     }
  205.     return mid;
  206. }
  207.  
  208. template<typename T, typename key_compare >
  209. void _partial_inplace_quicksort( T first, T last, key_compare comp )
  210. {
  211.     size_t s = last - first;
  212.     // sort only if the list is smaller than our limit.. else it's too small for
  213.     // us to bother.. caller would take care of it using some other stupid algo..
  214.     if( 16 > s )
  215.     {
  216.         // only one call to insertion_sort(), after whole array is partially sorted
  217.         // using quicksort().
  218.         // insertion_sort(first, last, pred);
  219.         return ;
  220.     }
  221.  
  222.     // select pivot.. use median 3
  223.     T mid = median3(first, last - 1, s, comp);
  224.     // partition
  225.     _partial_inplace_quicksort_partition(first, last, mid, comp);
  226.     // recurse..
  227.     _partial_inplace_quicksort(first, mid, comp);
  228.     // tail recurse..
  229.     _partial_inplace_quicksort(mid+1, last, comp);
  230.     // print_array(first, last, "_partial_inplace_quicksort(exit2)" );
  231. }
  232.  
  233. // ---------------- INSERTION SORT used above ----------------
  234.  
  235. template<typename T, typename key_compare>
  236. void insertion_sort( T first, T last, key_compare comp )
  237. {
  238.     // for each element in the array [first+1, last[
  239.     for( T j = first+1; j < last; j++)
  240.     {
  241.         typename std::iterator_traits<T>::value_type curr = *j;
  242.         T hole = j;
  243.         // keep moving all the elements comp(hole.e. > or <) hole to right
  244.         while( hole > first && comp(curr, *(hole-1)) )
  245.         {
  246.             *hole = *(hole-1);
  247.             --hole;
  248.         }
  249.         // insert curr at the correct position.
  250.         *hole = curr;
  251.     }
  252. }
  253.  
  254. template<typename T, typename key_compare = std::less<T>>
  255. class MySortAlgoTester
  256. {
  257.     key_compare comp;
  258.     std::vector<T> vec;
  259.     typedef typename std::vector<T>::iterator vecIter;
  260.     std::vector<T> vec_copy;
  261.     size_t m_numElements;
  262.     bool is_sorted(vecIter first, vecIter last)
  263.     {
  264.         vecIter sFirst = first;
  265.         for(vecIter next = first+1; next != last;)
  266.             // '>' associativity: left to right
  267.             // ++ has precedence over >
  268.             if( !comp(*(first++), *(next++)) )
  269.             {
  270.                 if(*(next-1) == *(first-1))
  271.                 {
  272.                     continue;
  273.                 }
  274.                 print_array(sFirst, last, "is_sorted() returning false: ");
  275.                 std::cout << "comp(" << *(first-1) << ", " << *(next-1) << ") = false && "
  276.                     << *(next-1) << " != " << *(first-1) << std::endl ;
  277.                 return false;
  278.             }
  279.  
  280.         return true;
  281.     }
  282.  
  283.     public:
  284.     MySortAlgoTester(size_t numElements) : m_numElements(numElements)
  285.     {
  286.         srand(123456789L);
  287.         vec.resize(m_numElements);
  288.         vec_copy.resize(m_numElements);
  289.         //		std::generate(vec.begin(), vec.end(), rand);
  290.         for(size_t i = 0; i < vec.size(); i++)
  291.         {
  292.             vec[i] = rand() % (m_numElements * 2);
  293.             vec_copy[i] = vec[i];
  294.         }
  295.     }
  296.  
  297.     ~MySortAlgoTester()
  298.     {
  299.     }
  300.  
  301.     void reset()
  302.     {
  303.         // copy the data back so next algo can be tested with same array.
  304.         std::copy(vec_copy.begin(), vec_copy.end(), vec.begin());
  305.         for(size_t i = 0; i < vec_copy.size(); i++)
  306.         {
  307.             vec[i] = vec_copy[i];
  308.         }
  309.         // std::copy(vec_copy.begin(), vec_copy.end(),  vec);
  310.     }
  311.  
  312.     double test( void (*sort_func)(typename std::vector<T>::iterator first, typename std::vector<T>::iterator last, key_compare pred), const char* name )
  313.     {
  314.         std::cout << "START Testing: " << name << ". With --- " << m_numElements << " elements." << std::endl;
  315.         startClock();
  316.  
  317.         sort_func(vec.begin(), vec.end(), comp);
  318.         double ms = getClock();
  319.         if(!std::is_sorted(vec.begin(), vec.end()))
  320.         {
  321.             std::cout << name << " did not sort the array." << std::endl;
  322.             // throw string(name) + " did not sort the array.";
  323.         }
  324.         std::cout << "DONE Testing: " << name << ". Time taken (ms): " << ms << std::endl;
  325.         return ms;
  326.     }
  327.  
  328.     double test( void (*sort_func)(typename std::vector<T>::iterator first, typename std::vector<T>::iterator last), const char* name )
  329.     {
  330.         std::cout << "START Testing: " << name << ". With --- " << m_numElements << " elements." << std::endl;
  331.         startClock();
  332.  
  333.         sort_func(vec.begin(), vec.end());
  334.         double ms = getClock();
  335.         if(!MySortAlgoTester::is_sorted(vec.begin(), vec.end()))
  336.         {
  337.             std::cout << name << " did not sort the array." << std::endl;
  338.             // throw string(name) + " did not sort the array.";
  339.         }
  340.         std::cout << "DONE Testing: " << name << ". Time taken (ms): " << ms << std::endl;
  341.         return ms;
  342.     }
  343. };
  344.  
  345.  
  346. int main ()
  347. {
  348.     srand(123456789L);
  349.     size_t numElements = 4;
  350.     std::vector<const char*> algoNames;
  351.     std::map<double, std::vector<double>> results;
  352.     int numTests = 0;
  353.     while( (numElements *= 2) <= 4096*16 )
  354.     {
  355.         MySortAlgoTester<int> tester(numElements);
  356.         results[numElements] = std::vector<double>();
  357. #if 0
  358.         algoNames.push_back("insertion_sort");
  359.         results[numElements].push_back(tester.test(insertion_sort, "insertion_sort"));
  360.         tester.reset();
  361. #elif 0
  362.         algoNames.push_back("quick");
  363.         results[numElements].push_back(tester.test(quicksort, "quicksort"));
  364.         tester.reset();
  365. #elif 1
  366.         algoNames.push_back("mixed_quicksort");
  367.         results[numElements].push_back(tester.test(mixed_quicksort, "mixed_quicksort"));
  368. #endif
  369.     }
  370.     // --- print the results...
  371. }
  372.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
In file included from /usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/type_traits:40,
                 from prog.cpp:8:
/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/c++0x_warning.h:36:2: error: #error This file requires compiler and library support for the upcoming ISO C++ standard, C++0x. This support is currently experimental, and must be enabled with the -std=c++0x or -std=gnu++0x compiler options.
In file included from prog.cpp:8:
/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/type_traits:82: error: template argument 1 is invalid
/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/type_traits:106: error: template argument 1 is invalid
/usr/lib/gcc/i686-pc-linux-gnu/4.3.4/include/g++-v4/type_traits:136: error: expected unqualified-id before ‘&&’ token
prog.cpp:254: warning: ‘>>’ operator will be treated as two right angle brackets in C++0x
prog.cpp:254: warning: suggest parentheses around ‘>>’ expression
prog.cpp:254: error: spurious ‘>>’, use ‘>’ to terminate a template argument list
prog.cpp:256: error: definition of ‘class MySortAlgoTester’ inside template parameter list
prog.cpp:343: error: two or more data types in declaration of ‘type name’
prog.cpp:343: error: expected ‘>’ before ‘;’ token
prog.cpp:343: error: expected unqualified-id before ‘;’ token
prog.cpp: In function ‘int main()’:
prog.cpp:351: error: ‘>>’ should be ‘> >’ within a nested template argument list
prog.cpp:355: error: ‘MySortAlgoTester’ was not declared in this scope
prog.cpp:355: error: expected primary-expression before ‘int’
prog.cpp:355: error: expected `;' before ‘int’
prog.cpp:367: error: ‘tester’ was not declared in this scope
prog.cpp:352: warning: unused variable ‘numTests’
stdout
copy 
Standard output is empty
https://ideone.com/LgAgs
language:
C++ (gcc 8.3)
created:
13 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!