1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
| #ifndef lessThan_H #define lessThan_H
template < typename Comparable > inline bool lessThan( const Comparable a, const Comparable b ){ return a < b; }
#endif
#ifndef QuickSort_H #define QuickSort_H #include "Swap.hpp" #include "InsertSort.hpp" #include <cstdlib>
template < typename Comparable_Ptr, typename Comparator > void quickSort( const Comparable_Ptr start, const Comparable_Ptr end, Comparator cmp ){ const auto delta = end - start; if( delta > 16 ){ swap( *start, *( start + rand() % ( int )( end - start ) ) ); auto judging = start + 1; auto less = start - 1; auto eq = start; auto criterion = *start; while( judging <= end ){ if( cmp( criterion, *judging ) == cmp( *judging, criterion ) ){ ++eq; swap( *judging, *eq); }else if( cmp( *judging, criterion ) ){ ++less; ++eq; *less = *judging; *judging = *eq; *eq = criterion; } ++judging; } ++eq; quickSort( start, less, cmp ); quickSort( eq, end, cmp );
}else{ if( delta > 0 ){ insertSort( start, end, cmp); } } }
#endif
|