Paste will expire never.
- /*THIS IMPLEMENTATION CONTAINS AN ERROR.*/
- /*
- Flat qsort
- Version 1.0
- This code is Public Domain
- This is the implementation of flat qsort.
- Flat qsort is a sorting algorithm which has the following properties:
- 1. Time complexity: O(n*log(n)) worst-case and best-case.
- 2. Auxiliary space: O(1) worst-case and best-case.
- 3. Works on any collection, that implements advancing to the next element in O(1) time.
- 4. Is not stable.
- 5. Is not adaptive (it follows from 1).
- Algorithm explanation:
- Let's start with the following, slightly quaint, version of quick sort:
- template <typename Iterator>
- void qsort(Iterator b,Iterator e)
- {
- if(b==e) return;
- if(std::is_sorted(b,e)) return;
- Iterator pivot=select_pivot(b,e);
- std::pair<Iterator,Iterator> pivot_range=partition_range(b,e,pivot);
- qsort(b,pivot_range.first);
- qsort(pivot_range.first,pivot_range.second);
- qsort(pivot_range.second,e);
- }
- Some observations:
- 1. Input is split in 3 blocks: less than pivot, equal, and greater.
- 2. Blocks do not overlap.
- 3. Blocks cover entire range.
- 3. Blocks are strictly ordered: any element of any block is strictly less than
- any following block.
- If we consider all recursive calls at a given depth, we observe that they
- collectively transform strictly ordered sequence of unsorted blocks (at the
- start the only block consists of entire input) into a strictly ordered
- sequence of unsorted blocks, possibly of smaller sizes. The sequence (both
- before and after transformation) spans entire input.
- From this we obtain the idea of the non-recursive version.
- While input is not sorted, we iterate it, splitting each block encountered
- in 3.
- Since blocks are strictly ordered, we can identify them without any extra
- space. We postulate that initial element of the block is its largest element,
- and enforce this property after splitting. Thanks to the strict ordering
- anything larger than the beginning of the block is the beginning of the
- next block. During this phase we also need to check for the end of
- input.
- To defeat the O(n^2) worst-case time complexity we need to choose the
- pivot in a reasonably optimal manner. Median of medians is one such choice.
- Note. Technically C++ Standard does not guarantee O(1) space complexity of
- the std::distance, std::next, std::swap, std::is_sorted operations.
- Implementing them in a way, that provides such a guarantee is left
- as an exercise to the reader. End of note.
- Directions for future research:
- 1. Is there a modification of this algorithm that is stable?
- 2. Can requirement of O(1) advance cost be lowered to amortized O(1)?
- */
- #include <cstdio>
- #include <ctime>
- #include <random>
- #include <utility>
- #include <algorithm>
- #include <vector>
- #include <forward_list>
- using std::pair;
- using std::next;
- using std::swap;
- template<typename ForwardIterator>
- void bubble_sort(ForwardIterator b,ForwardIterator e)
- {
- size_t n=std::distance(b,e);
- for(size_t i=0;i<n;++i)
- for(ForwardIterator j=b,k;j!=e;j=k)
- {
- k=next(j);
- if(k!=e&&*k<*j) swap(*j,*k);
- }
- }
- template<typename ForwardIterator>
- ForwardIterator select_pivot(ForwardIterator b,ForwardIterator e)
- {
- size_t n;
- while((n=std::distance(b,e))>4)
- {
- ForwardIterator src_b=b,src_e,dst=b;
- while(src_b!=e)
- {
- size_t m;
- src_e=src_b;
- for(size_t i=0;i<5&&src_e!=e;++i)
- src_e=next(src_e);
- m=std::distance(src_b,src_e);
- bubble_sort(src_b,src_e);
- swap(*dst,*(next(src_b,m/2)));
- src_b=src_e;
- dst=next(dst);
- }
- e=dst;
- }
- bubble_sort(b,e);
- return next(b,n/2);
- }
- template<typename ForwardIterator>
- std::pair<ForwardIterator,ForwardIterator> partition_range(ForwardIterator b,ForwardIterator e,ForwardIterator pivot)
- {
- std::pair<ForwardIterator,ForwardIterator> ret;
- size_t count_total=0,count_less=0,count_greater=0;
- for(ForwardIterator i=b;i!=e;i=next(i))
- {
- count_total+=1;
- count_less+=(*i<*pivot);
- count_greater+=(*pivot<*i);
- }
- ret.first=next(b,count_less);
- ret.second=next(b,count_total-count_greater);
- swap(*pivot,*(ret.first));
- for(ForwardIterator i=b,j=ret.first;i!=ret.first&&j!=e;)
- {
- while(i!=ret.first&&(*i<*(ret.first))) i=next(i);
- while(j!=e&&(!(*j<*(ret.first)))) j=next(j);
- if(i!=ret.first&&j!=e) swap(*i,*j);
- }
- for(ForwardIterator i=ret.first,j=ret.second;i!=ret.second&&j!=e;)
- {
- while(i!=ret.second&&(!(*ret.first<*i))) i=next(i);
- while(j!=e&&(*(ret.first)<*j)) j=next(j);
- if(i!=ret.second&&j!=e) swap(*i,*j);
- }
- return ret;
- }
- template<typename ForwardIterator>
- void blockify(ForwardIterator b,ForwardIterator e)
- {
- for(ForwardIterator i=b;i!=e;i=next(i))
- if(*b<*i) swap(*b,*i);
- }
- template<typename ForwardIterator>
- ForwardIterator block_range(ForwardIterator b,ForwardIterator e)
- {
- ForwardIterator ret=b;
- while(ret!=e&&(!(*b<*ret))) ret=next(ret);
- return ret;
- }
- template <typename ForwardIterator>
- void flat_qsort(ForwardIterator b,ForwardIterator e)
- {
- ForwardIterator local_b,local_e;
- ForwardIterator pivot;
- pair<ForwardIterator,ForwardIterator> pivot_range;
- if(b==e) return;
- blockify(b,e);
- while(!std::is_sorted(b,e))
- {
- local_b=b;
- while(local_b!=e)
- {
- local_e=block_range(local_b,e);
- pivot=select_pivot(local_b,local_e);
- pivot_range=partition_range(local_b,local_e,pivot);
- blockify(local_b,pivot_range.first);
- blockify(pivot_range.second,local_e);
- local_b=local_e;
- }
- }
- }
- //=============================================================================
- std::vector<int> generate_random_vector(int n,pair<int,int> range)
- {
- std::vector<int> ret(n);
- std::mt19937 rng;
- std::uniform_int_distribution<int> distribution(range.first,range.second);
- for(int i=0;i<n;++i)
- ret[i]=distribution(rng);
- return ret;
- }
- std::forward_list<int> generate_random_forward_list(int n,pair<int,int> range)
- {
- std::vector<int> elements=generate_random_vector(n,range);
- return std::forward_list<int>(elements.begin(),elements.end());
- }
- //=============================================================================
- int main()
- {
- int sizes[]=
- {
- 0,
- 1,
- 2,
- 4,
- 8,
- 10,
- 32,
- 100,
- 1024,
- 25000,
- 65536,
- 100000,
- 1000000
- };
- int ranges[]=
- {
- 0,
- 1,
- 2,
- 2,
- 5,
- 7,
- 10,
- 100,
- 10000,
- 1000000,
- 2000000000
- };
- for(size_t i=0;i<sizeof(sizes)/sizeof(sizes[0]);++i)
- for(size_t j=0;j<sizeof(ranges)/sizeof(ranges[0]);++j)
- {
- printf("Testing: size=%d, range=[0..%d].\n",sizes[i],ranges[j]);
- std::vector<int> test_vector=generate_random_vector(sizes[i],{0,ranges[j]});
- std::forward_list<int> test_list=generate_random_forward_list(sizes[i],{0,ranges[j]});
- flat_qsort(test_vector.begin(),test_vector.end());
- flat_qsort(test_list.begin(),test_list.end());
- printf("[vector] is_sorted: %s\n",std::is_sorted(test_vector.begin(),test_vector.end())?"true":"false");
- printf("[list] is_sorted: %s\n",std::is_sorted(test_list.begin(),test_list.end())?"true":"false");
- }
- return 0;
- }