#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
template < typename It>
void print_subrange( It first, It last, It subfirst, It sublast) {
It c = first;
for ( ; c! = subfirst; ++ c)
std:: cout << ' ' << * c;
std:: cout << '|' ;
if ( subfirst ! = last)
std:: cout << * c;
for ( ++ c ; c! = sublast; ++ c)
std:: cout << ' ' << * c;
std:: cout << '|' ;
for ( ; c! = last; ++ c)
std:: cout << * c << ' ' ;
std:: cout << '\n ' ;
}
template < class BidiIter, class CompatitorType>
void NotQuickSort( BidiIter first, BidiIter last, CompatitorType&& comparitor)
{
if ( first== last) return ;
//move the maximum element to the front
BidiIter max_it = std:: max_element ( first,last,comparitor) ;
if ( max_it ! = first)
std:: iter_swap ( first, max_it) ;
BidiIter cur_begin = first;
BidiIter cur_end = last;
//current state is a large element A followed by a bunch of elements less than or equal to A. (I call this a "chunk")
//After this may be a larger element B followed by a bunch of elements greater than A but less than or equal to B.
//etc etc until the end of the data
while ( cur_begin ! = last) {
//if we don't know where the end of the current chunk is, simply search for the first element greater than the first element
BidiIter pivot_it = std:: next ( cur_begin) ;
if ( cur_begin == cur_end) {
auto && max_value = * cur_begin;
cur_end = std:: find_if ( pivot_it, last, [ & comparitor,& max_value] ( const auto & e) { return comparitor( max_value,e) ; } ) ;
}
//print_subrange(first, last, cur_begin, cur_end); //DEBUGGING PRINT HERE
//if the chunk only has the "large" element, skip to the next chunk.
//(cur_end ends up beingn equal to cur_begin, which triggers a search for the end)
if ( pivot_it == cur_end) {
++ cur_begin;
continue ;
}
//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
//(cur_end ends up beingn equal to cur_begin, which triggers a search for the end)
BidiIter subrange_begin = std:: next ( pivot_it) ;
if ( subrange_begin == cur_end) {
std:: iter_swap ( cur_begin, pivot_it) ;
++ cur_begin;
++ cur_begin;
continue ;
}
//here's the "recursive" step. We're going to split the "less than or equal" elements into two chunks.
//the first element, A, is the largest in this chunk, and will be the "large" element for the right half.
//we're going to pick the second element, B, to be our pivot, and thus our large element for the left half.
//so partition the "smaller" elements based on the value of B, the pivot.
auto && pivot_value = * pivot_it;
BidiIter mid = std:: partition ( subrange_begin, cur_end, [ & comparitor,& pivot_value] ( const auto & e) { return ! comparitor( pivot_value,e) ; } ) ;
//we're going to want B to be the first element, so swap A and B
std:: iter_swap ( cur_begin, pivot_it) ;
//if no elements are less than B, then A (at it's new position) to the end of the chunk is our next chunk
if ( subrange_begin == mid) {
++ cur_begin;
continue ;
}
//otherwise, swap A to the middle of the partition.
-- mid;
std:: iter_swap ( pivot_it, mid) ;
//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]
//so we simply continue, operating on the B chunk, whcih ends at the partition point.
cur_end = mid;
}
}
template < class BidiIter>
void NotQuickSort( BidiIter first, BidiIter last)
{ return NotQuickSort( first,last,std:: less < void > ( ) ) ; }
template < class Container, class CompatitorType>
void NotQuickSort( Container& c, CompatitorType&& comparitor)
{ return NotQuickSort( std:: begin ( c) , std:: end ( c) , comparitor) ; }
template < class Container>
void NotQuickSort( Container& c)
{ return NotQuickSort( std:: begin ( c) , std:: end ( c) , std:: less < void > ( ) ) ; }
void TestNotQuickSort( std:: vector < int > c) {
NotQuickSort( c.begin ( ) , c.end ( ) , std:: less < int > { } ) ;
assert ( std:: is_sorted ( c.begin ( ) , c.end ( ) ) ) ;
}
int main( ) {
TestNotQuickSort( { } ) ;
TestNotQuickSort( { 0 } ) ;
TestNotQuickSort( { 0 , 0 } ) ;
TestNotQuickSort( { 0 , 1 } ) ;
TestNotQuickSort( { 1 , 0 } ) ;
TestNotQuickSort( { 0 , 0 , 0 } ) ;
TestNotQuickSort( { 0 , 0 , 1 } ) ;
TestNotQuickSort( { 0 , 1 , 0 } ) ;
TestNotQuickSort( { 1 , 0 , 0 } ) ;
TestNotQuickSort( { 0 , 1 , 1 } ) ;
TestNotQuickSort( { 1 , 0 , 1 } ) ;
TestNotQuickSort( { 1 , 1 , 0 } ) ;
TestNotQuickSort( { 0 , 1 , 2 } ) ;
TestNotQuickSort( { 0 , 2 , 1 } ) ;
TestNotQuickSort( { 1 , 0 , 2 } ) ;
TestNotQuickSort( { 1 , 2 , 0 } ) ;
TestNotQuickSort( { 2 , 0 , 1 } ) ;
TestNotQuickSort( { 2 , 1 , 0 } ) ;
std:: cout << "PASS" ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8dmVjdG9yPgojaW5jbHVkZSA8Y2Fzc2VydD4KIAogdGVtcGxhdGU8dHlwZW5hbWUgSXQ+CnZvaWQgcHJpbnRfc3VicmFuZ2UoSXQgZmlyc3QsIEl0IGxhc3QsIEl0IHN1YmZpcnN0LCBJdCBzdWJsYXN0KSB7CiAgICBJdCBjID0gZmlyc3Q7CiAgICBmb3IoIDsgYyE9c3ViZmlyc3Q7ICsrYykKICAgICAgICBzdGQ6OmNvdXQgPDwgJyAnIDw8ICpjOwogICAgc3RkOjpjb3V0IDw8ICd8JzsKICAgIGlmIChzdWJmaXJzdCAhPSBsYXN0KQogICAgICAgIHN0ZDo6Y291dCA8PCAqYzsKICAgIGZvcigrK2MgOyBjIT1zdWJsYXN0OyArK2MpCiAgICAgICAgc3RkOjpjb3V0IDw8ICcgJyA8PCAqYzsKICAgIHN0ZDo6Y291dCA8PCAnfCc7CiAgICBmb3IoIDsgYyE9bGFzdDsgKytjKQogICAgICAgIHN0ZDo6Y291dCA8PCAqYyA8PCAnICc7CiAgICBzdGQ6OmNvdXQgPDwgJ1xuJzsKfQogCiB0ZW1wbGF0ZSA8Y2xhc3MgQmlkaUl0ZXIsIGNsYXNzIENvbXBhdGl0b3JUeXBlPgogdm9pZCBOb3RRdWlja1NvcnQoQmlkaUl0ZXIgZmlyc3QsIEJpZGlJdGVyIGxhc3QsIENvbXBhdGl0b3JUeXBlJiYgY29tcGFyaXRvcikKIHsKICAgIGlmKGZpcnN0PT1sYXN0KSByZXR1cm47CiAgICAvL21vdmUgdGhlIG1heGltdW0gZWxlbWVudCB0byB0aGUgZnJvbnQKICAgIEJpZGlJdGVyIG1heF9pdCA9IHN0ZDo6bWF4X2VsZW1lbnQoZmlyc3QsbGFzdCxjb21wYXJpdG9yKTsKICAgIGlmIChtYXhfaXQgIT0gZmlyc3QpCiAgICAgICAgc3RkOjppdGVyX3N3YXAoZmlyc3QsIG1heF9pdCk7CiAgICBCaWRpSXRlciBjdXJfYmVnaW4gPSBmaXJzdDsKICAgIEJpZGlJdGVyIGN1cl9lbmQgPSBsYXN0OwogICAgLy9jdXJyZW50IHN0YXRlIGlzIGEgbGFyZ2UgZWxlbWVudCBBIGZvbGxvd2VkIGJ5IGEgYnVuY2ggb2YgZWxlbWVudHMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIEEuIChJIGNhbGwgdGhpcyBhICJjaHVuayIpCiAgICAvL0FmdGVyIHRoaXMgbWF5IGJlIGEgbGFyZ2VyIGVsZW1lbnQgQiBmb2xsb3dlZCBieSBhIGJ1bmNoIG9mIGVsZW1lbnRzIGdyZWF0ZXIgdGhhbiBBIGJ1dCBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gQi4KICAgIC8vZXRjIGV0YyB1bnRpbCB0aGUgZW5kIG9mIHRoZSBkYXRhCiAgICB3aGlsZShjdXJfYmVnaW4gIT0gbGFzdCkgewogICAgICAgIC8vaWYgd2UgZG9uJ3Qga25vdyB3aGVyZSB0aGUgZW5kIG9mIHRoZSBjdXJyZW50IGNodW5rIGlzLCBzaW1wbHkgc2VhcmNoIGZvciB0aGUgZmlyc3QgZWxlbWVudCBncmVhdGVyIHRoYW4gdGhlIGZpcnN0IGVsZW1lbnQKICAgICAgICBCaWRpSXRlciBwaXZvdF9pdCA9IHN0ZDo6bmV4dChjdXJfYmVnaW4pOwogICAgICAgIGlmIChjdXJfYmVnaW4gPT0gY3VyX2VuZCkgewogICAgICAgICAgICBhdXRvJiYgbWF4X3ZhbHVlID0gKmN1cl9iZWdpbjsKICAgICAgICAgICAgY3VyX2VuZCA9IHN0ZDo6ZmluZF9pZihwaXZvdF9pdCwgbGFzdCwgWyZjb21wYXJpdG9yLCZtYXhfdmFsdWVdKGNvbnN0IGF1dG8mIGUpe3JldHVybiBjb21wYXJpdG9yKG1heF92YWx1ZSxlKTt9KTsKICAgICAgICB9CiAgICAgICAgLy9wcmludF9zdWJyYW5nZShmaXJzdCwgbGFzdCwgY3VyX2JlZ2luLCBjdXJfZW5kKTsgLy9ERUJVR0dJTkcgUFJJTlQgSEVSRQogICAgICAgIC8vaWYgdGhlIGNodW5rIG9ubHkgaGFzIHRoZSAibGFyZ2UiIGVsZW1lbnQsIHNraXAgdG8gdGhlIG5leHQgY2h1bmsuCiAgICAgICAgLy8oY3VyX2VuZCBlbmRzIHVwIGJlaW5nbiBlcXVhbCB0byBjdXJfYmVnaW4sIHdoaWNoIHRyaWdnZXJzIGEgc2VhcmNoIGZvciB0aGUgZW5kKQogICAgICAgIGlmIChwaXZvdF9pdCA9PSBjdXJfZW5kKSB7CiAgICAgICAgICAgICsrY3VyX2JlZ2luOwogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICB9CiAgICAgICAgLy9pZiB0aGUgY2h1bmsgaGFzIGEgImxhcmdlIiBlbGVtZW50IGZvbGxvd2VkIGJ5IG9uZSBvdGhlciBlbGVtZW50IGxlc3MgdGhhbiBvciBlcXVhbCB0byBpdCwgc3dhcCB0aGVtIGFuZCBza2lwIHRvIHRoZSBuZXh0IGNodW5rCiAgICAgICAgLy8oY3VyX2VuZCBlbmRzIHVwIGJlaW5nbiBlcXVhbCB0byBjdXJfYmVnaW4sIHdoaWNoIHRyaWdnZXJzIGEgc2VhcmNoIGZvciB0aGUgZW5kKQogICAgICAgIEJpZGlJdGVyIHN1YnJhbmdlX2JlZ2luID0gc3RkOjpuZXh0KHBpdm90X2l0KTsKICAgICAgICBpZiAoc3VicmFuZ2VfYmVnaW4gPT0gY3VyX2VuZCkgewogICAgICAgICAgICBzdGQ6Oml0ZXJfc3dhcChjdXJfYmVnaW4sIHBpdm90X2l0KTsKICAgICAgICAgICAgKytjdXJfYmVnaW47CiAgICAgICAgICAgICsrY3VyX2JlZ2luOwogICAgICAgICAgICBjb250aW51ZTsKICAgICAgICB9CiAgICAgICAgLy9oZXJlJ3MgdGhlICJyZWN1cnNpdmUiIHN0ZXAuICBXZSdyZSBnb2luZyB0byBzcGxpdCB0aGUgImxlc3MgdGhhbiBvciBlcXVhbCIgZWxlbWVudHMgaW50byB0d28gY2h1bmtzLgogICAgICAgIC8vdGhlIGZpcnN0IGVsZW1lbnQsIEEsIGlzIHRoZSBsYXJnZXN0IGluIHRoaXMgY2h1bmssIGFuZCB3aWxsIGJlIHRoZSAibGFyZ2UiIGVsZW1lbnQgZm9yIHRoZSByaWdodCBoYWxmLgogICAgICAgIC8vd2UncmUgZ29pbmcgdG8gcGljayB0aGUgc2Vjb25kIGVsZW1lbnQsIEIsIHRvIGJlIG91ciBwaXZvdCwgYW5kIHRodXMgb3VyIGxhcmdlIGVsZW1lbnQgZm9yIHRoZSBsZWZ0IGhhbGYuCiAgICAgICAgLy9zbyBwYXJ0aXRpb24gdGhlICJzbWFsbGVyIiBlbGVtZW50cyBiYXNlZCBvbiB0aGUgdmFsdWUgb2YgQiwgdGhlIHBpdm90LgogICAgICAgIGF1dG8mJiBwaXZvdF92YWx1ZSA9ICpwaXZvdF9pdDsKICAgICAgICBCaWRpSXRlciBtaWQgPSBzdGQ6OnBhcnRpdGlvbihzdWJyYW5nZV9iZWdpbiwgY3VyX2VuZCwgIFsmY29tcGFyaXRvciwmcGl2b3RfdmFsdWVdKGNvbnN0IGF1dG8mIGUpe3JldHVybiAhY29tcGFyaXRvcihwaXZvdF92YWx1ZSxlKTt9KTsKICAgICAgICAvL3dlJ3JlIGdvaW5nIHRvIHdhbnQgQiB0byBiZSB0aGUgZmlyc3QgZWxlbWVudCwgc28gc3dhcCBBIGFuZCBCCiAgICAgICAgc3RkOjppdGVyX3N3YXAoY3VyX2JlZ2luLCBwaXZvdF9pdCk7CiAgICAgICAgLy9pZiBubyBlbGVtZW50cyBhcmUgbGVzcyB0aGFuIEIsIHRoZW4gQSAoYXQgaXQncyBuZXcgcG9zaXRpb24pIHRvIHRoZSBlbmQgb2YgdGhlIGNodW5rIGlzIG91ciBuZXh0IGNodW5rCiAgICAgICAgaWYgKHN1YnJhbmdlX2JlZ2luID09IG1pZCkgewogICAgICAgICAgICArK2N1cl9iZWdpbjsKICAgICAgICAgICAgY29udGludWU7CiAgICAgICAgfQogICAgICAgIC8vb3RoZXJ3aXNlLCBzd2FwIEEgdG8gdGhlIG1pZGRsZSBvZiB0aGUgcGFydGl0aW9uLiAgCiAgICAgICAgLS1taWQ7CiAgICAgICAgc3RkOjppdGVyX3N3YXAocGl2b3RfaXQsIG1pZCk7CiAgICAgICAgLy9ub3cgaXQncyBbQl1bRWxlbWVudHMgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIEJdW0FdW0VsZW1lbnRzIGdyZWF0ZXIgdGhhbiBCIGJ1dCBsZXNzIHRoYW4gb3IgZXF1YWwgdG8gQV1bQ11bRWxlbWVudHMgZ3JlYXRlciB0aGFuIEEgYnV0IGxlc3MgdGhhbiBvciBlcXVhbCB0byBDXQogICAgICAgIC8vc28gd2Ugc2ltcGx5IGNvbnRpbnVlLCBvcGVyYXRpbmcgb24gdGhlIEIgY2h1bmssIHdoY2loIGVuZHMgYXQgdGhlIHBhcnRpdGlvbiBwb2ludC4KICAgICAgICBjdXJfZW5kID0gbWlkOwogICAgfQogfQogdGVtcGxhdGUgPGNsYXNzIEJpZGlJdGVyPgogdm9pZCBOb3RRdWlja1NvcnQoQmlkaUl0ZXIgZmlyc3QsIEJpZGlJdGVyIGxhc3QpCiB7cmV0dXJuIE5vdFF1aWNrU29ydChmaXJzdCxsYXN0LHN0ZDo6bGVzczx2b2lkPigpKTt9CiB0ZW1wbGF0ZSA8Y2xhc3MgQ29udGFpbmVyLCBjbGFzcyBDb21wYXRpdG9yVHlwZT4KIHZvaWQgTm90UXVpY2tTb3J0KENvbnRhaW5lciYgYywgQ29tcGF0aXRvclR5cGUmJiBjb21wYXJpdG9yKQoge3JldHVybiBOb3RRdWlja1NvcnQoc3RkOjpiZWdpbihjKSwgc3RkOjplbmQoYyksIGNvbXBhcml0b3IpO30KIHRlbXBsYXRlIDxjbGFzcyBDb250YWluZXI+CiB2b2lkIE5vdFF1aWNrU29ydChDb250YWluZXImIGMpCiB7cmV0dXJuIE5vdFF1aWNrU29ydChzdGQ6OmJlZ2luKGMpLCBzdGQ6OmVuZChjKSwgc3RkOjpsZXNzPHZvaWQ+KCkpO30KCgp2b2lkIFRlc3ROb3RRdWlja1NvcnQoc3RkOjp2ZWN0b3I8aW50PiBjKSB7CiAgICBOb3RRdWlja1NvcnQoYy5iZWdpbigpLCBjLmVuZCgpLCBzdGQ6Omxlc3M8aW50Pnt9KTsKICAgIGFzc2VydChzdGQ6OmlzX3NvcnRlZChjLmJlZ2luKCksIGMuZW5kKCkpKTsgICAgICAgIAp9CmludCBtYWluKCkgewogICAgVGVzdE5vdFF1aWNrU29ydCh7fSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHswfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHswLCAwfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHswLCAxfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHsxLCAwfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHswLCAwLCAwfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHswLCAwLCAxfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHswLCAxLCAwfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHsxLCAwLCAwfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHswLCAxLCAxfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHsxLCAwLCAxfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHsxLCAxLCAwfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHswLCAxLCAyfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHswLCAyLCAxfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHsxLCAwLCAyfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHsxLCAyLCAwfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHsyLCAwLCAxfSk7CiAgICBUZXN0Tm90UXVpY2tTb3J0KHsyLCAxLCAwfSk7CiAgICBzdGQ6OmNvdXQgPDwgIlBBU1MiOwp9Cg==