An Even Higher Performance Quicksort Implement

Article Directory

QuickSort.hpp

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

Swap.hpp

1
2
3
4
5
6
7
8
9
10
11
#ifndef Swap_H
#define Swap_H
#include <utility>
template <typename Object>
void swap( Object & a, Object & b ){
Object tmp = std::move(a);
a = std::move(b);
b = std::move(tmp);
}

#endif

InsertSort.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#ifndef InsertSort_H 
#define InsertSort_H

template <typename Comparable_Ptr, typename Comparator>
void insertSort(
const Comparable_Ptr start,
const Comparable_Ptr end,
Comparator cmp
){
for(auto i = start; i <= end; ++i ){
auto j = i - 1;
auto current = *i;
for( ; j >= start && cmp( current, *j ); --j ){
*(j + 1) = *j;
}
*( j + 1 ) = current;
}
}


#endif