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