fork download
copy 
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <cassert>
  5.  
  6.  template<typename It>
  7. void print_subrange(It first, It last, It subfirst, It sublast) {
  8.     It c = first;
  9.     for( ; c!=subfirst; ++c)
  10.         std::cout << ' ' << *c;
  11.     std::cout << '|';
  12.     if (subfirst != last)
  13.         std::cout << *c;
  14.     for(++c ; c!=sublast; ++c)
  15.         std::cout << ' ' << *c;
  16.     std::cout << '|';
  17.     for( ; c!=last; ++c)
  18.         std::cout << *c << ' ';
  19.     std::cout << '\n';
  20. }
  21.  
  22.  template <class BidiIter, class CompatitorType>
  23.  void NotQuickSort(BidiIter first, BidiIter last, CompatitorType&& comparitor)
  24.  {
  25.     if(first==last) return;
  26.     //move the maximum element to the front
  27.     BidiIter max_it = std::max_element(first,last,comparitor);
  28.     if (max_it != first)
  29.         std::iter_swap(first, max_it);
  30.     BidiIter cur_begin = first;
  31.     BidiIter cur_end = last;
  32.     //current state is a large element A followed by a bunch of elements less than or equal to A. (I call this a "chunk")
  33.     //After this may be a larger element B followed by a bunch of elements greater than A but less than or equal to B.
  34.     //etc etc until the end of the data
  35.     while(cur_begin != last) {
  36.         //if we don't know where the end of the current chunk is, simply search for the first element greater than the first element
  37.         BidiIter pivot_it = std::next(cur_begin);
  38.         if (cur_begin == cur_end) {
  39.             auto&& max_value = *cur_begin;
  40.             cur_end = std::find_if(pivot_it, last, [&comparitor,&max_value](const auto& e){return comparitor(max_value,e);});
  41.         }
  42.         //print_subrange(first, last, cur_begin, cur_end); //DEBUGGING PRINT HERE
  43.         //if the chunk only has the "large" element, skip to the next chunk.
  44.         //(cur_end ends up beingn equal to cur_begin, which triggers a search for the end)
  45.         if (pivot_it == cur_end) {
  46.             ++cur_begin;
  47.             continue;
  48.         }
  49.         //if the chunk has a "large" element followed by one other element less than or equal to it, swap them and skip to the next chunk
  50.         //(cur_end ends up beingn equal to cur_begin, which triggers a search for the end)
  51.         BidiIter subrange_begin = std::next(pivot_it);
  52.         if (subrange_begin == cur_end) {
  53.             std::iter_swap(cur_begin, pivot_it);
  54.             ++cur_begin;
  55.             ++cur_begin;
  56.             continue;
  57.         }
  58.         //here's the "recursive" step.  We're going to split the "less than or equal" elements into two chunks.
  59.         //the first element, A, is the largest in this chunk, and will be the "large" element for the right half.
  60.         //we're going to pick the second element, B, to be our pivot, and thus our large element for the left half.
  61.         //so partition the "smaller" elements based on the value of B, the pivot.
  62.         auto&& pivot_value = *pivot_it;
  63.         BidiIter mid = std::partition(subrange_begin, cur_end,  [&comparitor,&pivot_value](const auto& e){return !comparitor(pivot_value,e);});
  64.         //we're going to want B to be the first element, so swap A and B
  65.         std::iter_swap(cur_begin, pivot_it);
  66.         //if no elements are less than B, then A (at it's new position) to the end of the chunk is our next chunk
  67.         if (subrange_begin == mid) {
  68.             ++cur_begin;
  69.             continue;
  70.         }
  71.         //otherwise, swap A to the middle of the partition.  
  72.         --mid;
  73.         std::iter_swap(pivot_it, mid);
  74.         //now it's [B][Elements less than or equal to B][A][Elements greater than B but less than or equal to A][C][Elements greater than A but less than or equal to C]
  75.         //so we simply continue, operating on the B chunk, whcih ends at the partition point.
  76.         cur_end = mid;
  77.     }
  78.  }
  79.  template <class BidiIter>
  80.  void NotQuickSort(BidiIter first, BidiIter last)
  81.  {return NotQuickSort(first,last,std::less<void>());}
  82.  template <class Container, class CompatitorType>
  83.  void NotQuickSort(Container& c, CompatitorType&& comparitor)
  84.  {return NotQuickSort(std::begin(c), std::end(c), comparitor);}
  85.  template <class Container>
  86.  void NotQuickSort(Container& c)
  87.  {return NotQuickSort(std::begin(c), std::end(c), std::less<void>());}
  88.  
  89.  
  90. void TestNotQuickSort(std::vector<int> c) {
  91.     NotQuickSort(c.begin(), c.end(), std::less<int>{});
  92.     assert(std::is_sorted(c.begin(), c.end()));        
  93. }
  94. int main() {
  95.     TestNotQuickSort({});
  96.     TestNotQuickSort({0});
  97.     TestNotQuickSort({0, 0});
  98.     TestNotQuickSort({0, 1});
  99.     TestNotQuickSort({1, 0});
  100.     TestNotQuickSort({0, 0, 0});
  101.     TestNotQuickSort({0, 0, 1});
  102.     TestNotQuickSort({0, 1, 0});
  103.     TestNotQuickSort({1, 0, 0});
  104.     TestNotQuickSort({0, 1, 1});
  105.     TestNotQuickSort({1, 0, 1});
  106.     TestNotQuickSort({1, 1, 0});
  107.     TestNotQuickSort({0, 1, 2});
  108.     TestNotQuickSort({0, 2, 1});
  109.     TestNotQuickSort({1, 0, 2});
  110.     TestNotQuickSort({1, 2, 0});
  111.     TestNotQuickSort({2, 0, 1});
  112.     TestNotQuickSort({2, 1, 0});
  113.     std::cout << "PASS";
  114. }
  115.  
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
PASS
https://ideone.com/7dF7l1
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!