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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
|
#include <random>
#include <iostream>
#include <limits>
#include <chrono>
#include <ctime>
#include <vector>
#include <string>
#include <algorithm>
// utility
auto
now() -> std::string {
auto t = std::chrono::system_clock::to_time_t(std::chrono::system_clock::now());
std::string formatted_now = std::ctime(&t);
formatted_now.pop_back(); // remove newline
return formatted_now;
}
auto
write_vector(const std::vector<int>& x, const std::string& msg) -> void {
std::cout << msg << ":\n";
for (int n=0; n<x.size(); ++n) {
std::cout << x[n] << "\n";
}
std::cout << "\n";
}
auto random_vector(int size) {
std::random_device rd; //Will be used to obtain a seed for the random number engine
std::mt19937 gen(rd()); //Standard mersenne_twister_engine seeded with rd()
auto imin = std::numeric_limits<int>::min();
auto imax = std::numeric_limits<int>::max();
std::uniform_int_distribution<> dis(imin,imax);
std::vector<int> x(size);
for (int n=0; n<size; ++n) {
//Use dis to transform the random unsigned int generated by gen into an int in [imin,imax]
x[n] = dis(gen);
}
return x;
}
// algorithms
template<class I, class Pred> inline auto
// requires I is bidirectional iterator
bidirectional_partition(I first, I last, Pred p) -> I {
if (first == last) return last;
auto from_begin = first;
auto from_end = --last;
while (from_begin != from_end) {
while ( (from_begin != from_end) && p(*from_begin) ) { ++from_begin; }
while ( (from_begin != from_end) && !p(*from_end) ) { --from_end; }
std::iter_swap(from_begin,from_end);
}
if (p(*from_begin)) { ++from_begin; }
return from_begin;
}
template<class I> auto
// requires I is iterator
swap_pivot_with_first(I first, I) {
return *first;
// nothing to swap since the chosen pivot is first
}
template<class I> auto
// requires I is bidirectional iterator
quick_sort(I first, I last) -> void {
I next = std::next(first);
if (first == last) return;
if (next == last) return;
auto pivot = swap_pivot_with_first(first,last);
auto less_than_pivot = [&pivot](const auto& value){ return value < pivot; };
auto partition_point = bidirectional_partition(next,last,less_than_pivot);
I one_before_partition_point = std::prev(partition_point);
std::iter_swap(first,one_before_partition_point);
quick_sort(first, one_before_partition_point);
quick_sort(partition_point,last);
}
enum kind_of_sort {
handmade_quicksort,
stl_introsort,
stl_mergesort
};
int main() {
const int size = 100'000'000;
//const int size = 100;
const kind_of_sort type_de_tri = handmade_quicksort;
auto x = random_vector(size);
//write_vector(x,"Tableau non trié");
std::cout << now() << " - Tri ...\n";
switch(type_de_tri) {
case handmade_quicksort: {
quick_sort(x.begin(),x.end());
break;
}
case stl_introsort: {
sort(x.begin(),x.end());
break;
}
case stl_mergesort: {
stable_sort(x.begin(),x.end());
break;
}
}
std::cout << now() << " - Tri, fin.\n";
//write_vector(x,"Tableau trié");
} |
Envoyé par wolinn
Répondre avec citation
Partager