v 0. Pasted by Anonymous as cpp at 2014-12-27 08:19:32 MSK and set expiration to never.
v 1. Edited by Anonymous as cpp at 2014-12-27 22:32:18 MSK and set expiration to never.

Paste will expire never.

  1. /*THIS IMPLEMENTATION CONTAINS AN ERROR.*/
  2.  
  3. /*
  4. Flat qsort
  5. Version 1.0
  7. This code is Public Domain
  9. This is the implementation of flat qsort.
  10. Flat qsort is a sorting algorithm which has the following properties:
  11. 1. Time complexity: O(n*log(n)) worst-case and best-case.
  12. 2. Auxiliary space: O(1) worst-case and best-case.
  13. 3. Works on any collection, that implements advancing to the next element in O(1) time.
  14. 4. Is not stable.
  15. 5. Is not adaptive (it follows from 1).
  17. Algorithm explanation:
  19. Let's start with the following, slightly quaint, version of quick sort:
  21. template <typename Iterator>
  22. void qsort(Iterator b,Iterator e)
  23. {
  24.     if(b==e) return;
  25.     if(std::is_sorted(b,e)) return;
  26.     Iterator pivot=select_pivot(b,e);
  27.     std::pair<Iterator,Iterator> pivot_range=partition_range(b,e,pivot);
  28.     qsort(b,pivot_range.first);
  29.     qsort(pivot_range.first,pivot_range.second);
  30.     qsort(pivot_range.second,e);
  31. }
  33. Some observations:
  34. 1. Input is split in 3 blocks: less than pivot, equal, and greater.
  35. 2. Blocks do not overlap.
  36. 3. Blocks cover entire range.
  37. 3. Blocks are strictly ordered: any element of any block is strictly less than
  38. any following block.
  40. If we consider all recursive calls at a given depth, we observe that they
  41. collectively transform strictly ordered sequence of unsorted blocks (at the
  42. start the only block consists of entire input) into a strictly ordered
  43. sequence of unsorted blocks, possibly of smaller sizes. The sequence (both
  44. before and after transformation) spans entire input.
  46. From this we obtain the idea of the non-recursive version.
  47. While input is not sorted, we iterate it, splitting each block encountered
  48. in 3.
  49. Since blocks are strictly ordered, we can identify them without any extra
  50. space. We postulate that initial element of the block is its largest element,
  51. and enforce this property after splitting. Thanks to the strict ordering
  52. anything larger than the beginning of the block is the beginning of the
  53. next block. During this phase we also need to check for the end of
  54. input.
  55. To defeat the O(n^2) worst-case time complexity we need to choose the
  56. pivot in a reasonably optimal manner. Median of medians is one such choice.
  58. Note. Technically C++ Standard does not guarantee O(1) space complexity of
  59. the std::distance, std::next, std::swap, std::is_sorted operations.
  60. Implementing them in a way, that provides such a guarantee is left
  61. as an exercise to the reader. End of note.
  63. Directions for future research:
  65. 1. Is there a modification of this algorithm that is stable?
  66. 2. Can requirement of O(1) advance cost be lowered to amortized O(1)?
  67. */
  68.  
  69. #include <cstdio>
  70. #include <ctime>
  71. #include <random>
  72. #include <utility>
  73. #include <algorithm>
  74.  
  75. #include <vector>
  76. #include <forward_list>
  77.  
  78. using std::pair;
  79. using std::next;
  80. using std::swap;
  81.  
  82. template<typename ForwardIterator>
  83. void bubble_sort(ForwardIterator b,ForwardIterator e)
  84. {
  85.     size_t n=std::distance(b,e);
  86.     for(size_t i=0;i<n;++i)
  87.         for(ForwardIterator j=b,k;j!=e;j=k)
  88.         {
  89.             k=next(j);
  90.             if(k!=e&&*k<*j) swap(*j,*k);
  91.         }
  92. }
  93.  
  94. template<typename ForwardIterator>
  95. ForwardIterator select_pivot(ForwardIterator b,ForwardIterator e)
  96. {
  97.     size_t n;
  98.     while((n=std::distance(b,e))>4)
  99.     {
  100.         ForwardIterator src_b=b,src_e,dst=b;
  101.         while(src_b!=e)
  102.         {
  103.             size_t m;
  104.             src_e=src_b;
  105.             for(size_t i=0;i<5&&src_e!=e;++i)
  106.                 src_e=next(src_e);
  107.             m=std::distance(src_b,src_e);
  108.             bubble_sort(src_b,src_e);
  109.             swap(*dst,*(next(src_b,m/2)));
  110.             src_b=src_e;
  111.             dst=next(dst);
  112.         }
  113.         e=dst;
  114.     }
  115.     bubble_sort(b,e);
  116.     return next(b,n/2);
  117. }
  118.  
  119. template<typename ForwardIterator>
  120. std::pair<ForwardIterator,ForwardIterator> partition_range(ForwardIterator b,ForwardIterator e,ForwardIterator pivot)
  121. {
  122.     std::pair<ForwardIterator,ForwardIterator> ret;
  123.     size_t count_total=0,count_less=0,count_greater=0;
  124.     for(ForwardIterator i=b;i!=e;i=next(i))
  125.     {
  126.         count_total+=1;
  127.         count_less+=(*i<*pivot);
  128.         count_greater+=(*pivot<*i);
  129.     }
  130.     ret.first=next(b,count_less);
  131.     ret.second=next(b,count_total-count_greater);
  132.     swap(*pivot,*(ret.first));
  133.     for(ForwardIterator i=b,j=ret.first;i!=ret.first&&j!=e;)
  134.     {
  135.         while(i!=ret.first&&(*i<*(ret.first))) i=next(i);
  136.         while(j!=e&&(!(*j<*(ret.first)))) j=next(j);
  137.         if(i!=ret.first&&j!=e) swap(*i,*j);
  138.     }
  139.     for(ForwardIterator i=ret.first,j=ret.second;i!=ret.second&&j!=e;)
  140.     {
  141.         while(i!=ret.second&&(!(*ret.first<*i))) i=next(i);
  142.         while(j!=e&&(*(ret.first)<*j)) j=next(j);
  143.         if(i!=ret.second&&j!=e) swap(*i,*j);
  144.     }
  145.     return ret;
  146. }
  147.  
  148. template<typename ForwardIterator>
  149. void blockify(ForwardIterator b,ForwardIterator e)
  150. {
  151.     for(ForwardIterator i=b;i!=e;i=next(i))
  152.         if(*b<*i) swap(*b,*i);
  153. }
  154.  
  155. template<typename ForwardIterator>
  156. ForwardIterator block_range(ForwardIterator b,ForwardIterator e)
  157. {
  158.     ForwardIterator ret=b;
  159.     while(ret!=e&&(!(*b<*ret))) ret=next(ret);
  160.     return ret;
  161. }
  162.  
  163. template <typename ForwardIterator>
  164. void flat_qsort(ForwardIterator b,ForwardIterator e)
  165. {
  166.     ForwardIterator local_b,local_e;
  167.     ForwardIterator pivot;
  168.     pair<ForwardIterator,ForwardIterator> pivot_range;
  169.     if(b==e) return;
  170.     blockify(b,e);
  171.     while(!std::is_sorted(b,e))
  172.     {
  173.         local_b=b;
  174.         while(local_b!=e)
  175.         {
  176.             local_e=block_range(local_b,e);
  177.             pivot=select_pivot(local_b,local_e);
  178.             pivot_range=partition_range(local_b,local_e,pivot);
  179.             blockify(local_b,pivot_range.first);
  180.             blockify(pivot_range.second,local_e);
  181.             local_b=local_e;
  182.         }
  183.     }
  184. }
  185.  
  186. //=============================================================================
  187.  
  188. std::vector<int> generate_random_vector(int n,pair<int,int> range)
  189. {
  190.     std::vector<int> ret(n);
  191.     std::mt19937 rng;
  192.     std::uniform_int_distribution<int> distribution(range.first,range.second);
  193.     for(int i=0;i<n;++i)
  194.         ret[i]=distribution(rng);
  195.     return ret;
  196. }
  197.  
  198. std::forward_list<int> generate_random_forward_list(int n,pair<int,int> range)
  199. {
  200.     std::vector<int> elements=generate_random_vector(n,range);
  201.     return std::forward_list<int>(elements.begin(),elements.end());
  202. }
  203.  
  204. //=============================================================================
  205.  
  206. int main()
  207. {
  208.     int sizes[]=
  209.     {
  210.         0,
  211.         1,
  212.         2,
  213.         4,
  214.         8,
  215.         10,
  216.         32,
  217.         100,
  218.         1024,
  219.         25000,
  220.         65536,
  221.         100000,
  222.         1000000
  223.     };
  224.     int ranges[]=
  225.     {
  226.         0,
  227.         1,
  228.         2,
  229.         2,
  230.         5,
  231.         7,
  232.         10,
  233.         100,
  234.         10000,
  235.         1000000,
  236.         2000000000
  237.     };
  238.     for(size_t i=0;i<sizeof(sizes)/sizeof(sizes[0]);++i)
  239.         for(size_t j=0;j<sizeof(ranges)/sizeof(ranges[0]);++j)
  240.         {
  241.             printf("Testing: size=%d, range=[0..%d].\n",sizes[i],ranges[j]);
  242.             std::vector<int> test_vector=generate_random_vector(sizes[i],{0,ranges[j]});
  243.             std::forward_list<int> test_list=generate_random_forward_list(sizes[i],{0,ranges[j]});
  244.             flat_qsort(test_vector.begin(),test_vector.end());
  245.             flat_qsort(test_list.begin(),test_list.end());
  246.  
  247.             printf("[vector] is_sorted: %s\n",std::is_sorted(test_vector.begin(),test_vector.end())?"true":"false");
  248.             printf("[list] is_sorted: %s\n",std::is_sorted(test_list.begin(),test_list.end())?"true":"false");
  249.         }
  250.     return 0;
  251. }