Thrill  0.1
qsort.hpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * thrill/common/qsort.hpp
3  *
4  * Quicksort implementations with two and three pivots. Pretty much the
5  * algorithm of Yaroslavskiy (from Java) and Kushagra et al. (2014) at
6  * ALENEX. Some parts are also from libc++ which is available under the MIT
8  *
9  * Part of Project Thrill - http://project-thrill.org
10  *
11  * Copyright (C) 2014 Sebastian Wild <[email protected]>
12  * Copyright (C) 2014 Martin AumÃ¼ller <[email protected]>
13  * Copyright (C) 2014 Timo Bingmann <[email protected]>
14  *
16  ******************************************************************************/
17
18 #pragma once
21
22 #include <thrill/common/logger.hpp>
23
24 #include <algorithm>
25
26 namespace thrill {
27 namespace common {
28 namespace qsort_local {
29
30 //! Assigns a0 <- a1, a1 <- a2, and a2 <- a0.
31 template <typename ValueType>
32 void rotate3(ValueType& a0, ValueType& a1, ValueType& a2) {
33  ValueType tmp = std::move(a0);
34  a0 = std::move(a1);
35  a1 = std::move(a2);
36  a2 = std::move(tmp);
37 }
38
39 //! Assigns a0 <- a1, a1 <- a2, a2 <- a3, and a3 <- a0.
40 template <typename ValueType>
41 void rotate4(ValueType& a0, ValueType& a1, ValueType& a2, ValueType& a3) {
42  ValueType tmp = std::move(a0);
43  a0 = std::move(a1);
44  a1 = std::move(a2);
45  a2 = std::move(a3);
46  a3 = std::move(tmp);
47 }
48
49 //! Sort three items, stable, 2-3 compares, 0-2 swaps
50 template <typename Compare, typename Iterator>
51 void sort3(Iterator x, Iterator y, Iterator z, Compare cmp) {
52  using std::swap;
53
54  if (!cmp(*y, *x)) { // if x <= y
55  if (!cmp(*z, *y)) // if y <= z
56  return; // x <= y && y <= z
57  // x <= y && y > z
58  swap(*y, *z); // x <= z && y < z
59  if (cmp(*y, *x)) // if x > y
60  swap(*x, *y); // x < y && y <= z
61  return; // x <= y && y < z
62  }
63  if (cmp(*z, *y)) { // x > y, if y > z
64  swap(*x, *z); // x < y && y < z
65  return;
66  }
67  swap(*x, *y); // x > y && y <= z
68  // x < y && x <= z
69  if (cmp(*z, *y)) // if y > z
70  swap(*y, *z); // x <= y && y < z
71  // x <= y && y <= z
72 }
73
74 //! Sort four items, stable, 3-6 compares, 0-5 swaps
75 template <typename Compare, typename Iterator>
76 void sort4(Iterator x1, Iterator x2, Iterator x3, Iterator x4, Compare cmp) {
77  using std::swap;
78
79  sort3<Compare>(x1, x2, x3, cmp);
80  if (cmp(*x4, *x3)) {
81  swap(*x3, *x4);
82  if (cmp(*x3, *x2)) {
83  swap(*x2, *x3);
84  if (cmp(*x2, *x1)) {
85  swap(*x1, *x2);
86  }
87  }
88  }
89 }
90
91 //! Sort five items, 4-10 compares, 0-9 swaps
92 template <typename Compare, typename Iterator>
93 void sort5(Iterator x1, Iterator x2, Iterator x3,
94  Iterator x4, Iterator x5, Compare cmp) {
95  using std::swap;
96
97  sort4<Compare>(x1, x2, x3, x4, cmp);
98  if (cmp(*x5, *x4)) {
99  swap(*x4, *x5);
100  if (cmp(*x4, *x3)) {
101  swap(*x3, *x4);
102  if (cmp(*x3, *x2)) {
103  swap(*x2, *x3);
104  if (cmp(*x2, *x1)) {
105  swap(*x1, *x2);
106  }
107  }
108  }
109  }
110 }
111
112 template <typename Compare, typename Iterator>
113 void InsertionSort(Iterator left, Iterator right, Compare cmp) {
114  using value_type = typename std::iterator_traits<Iterator>::value_type;
115  using std::swap;
116
117  switch (right - left) {
118  case 0:
119  case 1:
120  return;
121  case 2:
122  if (cmp(*(--right), *left))
123  swap(*left, *right);
124  return;
125  case 3:
126  return qsort_local::sort3<Compare>(left, left + 1, left + 2, cmp);
127  case 4:
128  return qsort_local::sort4<Compare>(
129  left, left + 1, left + 2, left + 3, cmp);
130  case 5:
131  return qsort_local::sort5<Compare>(
132  left, left + 1, left + 2, left + 3, left + 4, cmp);
133  }
134
135  for (Iterator i = left + 1; i != right; ++i) {
136  Iterator j = i;
137  value_type t(std::move(*j));
138  for (Iterator k = i; k != left && cmp(t, *(--k)); --j)
139  *j = std::move(*k);
140  *j = std::move(t);
141  }
142 }
143
144 template <typename Iterator, typename Compare>
145 Iterator median3(Iterator a, Iterator b, Iterator c, Compare cmp) {
146  if (cmp(*a, *b)) {
147  if (cmp(*b, *c))
148  return b;
149  else if (cmp(*a, *c))
150  return c;
151  else
152  return a;
153  }
154  else {
155  if (cmp(*a, *c))
156  return a;
157  else if (cmp(*b, *c))
158  return c;
159  else
160  return b;
161  }
162 }
163
164 //! Sort _iterators_ by their content, used for sorting pivot samples.
165 template <typename Iterator, typename Compare>
166 void sort_samples(Iterator* A, size_t size, Compare cmp) {
167  for (size_t i = 1; i < size; i++) {
168  size_t j = i;
169  Iterator t = A[i];
170  while (j > 0) {
171  if (cmp(*t, *(A[j - 1]))) {
172  A[j] = A[j - 1];
173  j--;
174  }
175  else {
176  break;
177  }
178  }
179  A[j] = t;
180  }
181 }
182
183 } // namespace qsort_local
184
185 template <typename Compare, typename Iterator>
186 void qsort_two_pivots_yaroslavskiy(Iterator lo, Iterator hi, Compare cmp) {
187  using value_type = typename std::iterator_traits<Iterator>::value_type;
188  using std::swap;
189
190  if (hi - lo < 32)
191  return qsort_local::InsertionSort<Compare>(lo, hi, cmp);
192
193  size_t n = hi - lo;
194
195  Iterator samples[7] = {
196  lo + n * 1 / 8, lo + n * 2 / 8, lo + n * 3 / 8,
197  lo + n * 4 / 8, lo + n * 5 / 8, lo + n * 6 / 8, lo + n * 7 / 8
198  };
199
200  qsort_local::sort_samples(samples, 7, cmp);
201
202  swap(*lo, *(samples[2]));
203  swap(*(hi - 1), *(samples[4]));
204
205  const value_type p = *lo;
206  const value_type q = *(hi - 1);
207
208  Iterator l = lo + 1;
209  Iterator g = hi - 2;
210  Iterator k = l;
211
212  while (k <= g) {
213  if (cmp(*k, p)) {
214  swap(*k, *l);
215  ++l;
216  }
217  else if (!cmp(*k, q)) {
218  while (cmp(q, *g))
219  --g;
220
221  if (k < g) {
222  if (cmp(*g, p)) {
223  qsort_local::rotate3(*g, *k, *l);
224  ++l;
225  }
226  else {
227  swap(*k, *g);
228  }
229  --g;
230  }
231  }
232  ++k;
233  }
234  --l, ++g;
235  swap(*lo, *l);
236  swap(*(hi - 1), *g);
237
238  qsort_two_pivots_yaroslavskiy<Compare>(lo, l, cmp);
239  qsort_two_pivots_yaroslavskiy<Compare>(l + 1, g, cmp);
240  qsort_two_pivots_yaroslavskiy<Compare>(g + 1, hi, cmp);
241 }
242
243 template <typename Compare, typename Iterator>
244 void qsort_three_pivots(Iterator left, Iterator right, Compare cmp) {
245  using value_type = typename std::iterator_traits<Iterator>::value_type;
246  using std::swap;
247
248  size_t n = right - left;
249
250  if (n <= 32)
251  return qsort_local::InsertionSort(left, right, cmp);
252
253  Iterator samples[7] = {
254  left + n * 1 / 8, left + n * 2 / 8, left + n * 3 / 8,
255  left + n * 4 / 8, left + n * 5 / 8, left + n * 6 / 8, left + n * 7 / 8
256  };
257
258  qsort_local::sort_samples(samples, 7, cmp);
259
260  swap(*left, *(samples[1]));
261  swap(*(left + 1), *(samples[3]));
262  swap(*(right - 1), *(samples[5]));
263
264  Iterator i = left + 2;
265  Iterator j = i;
266
267  Iterator k = right - 2;
268  Iterator l = k;
269
270  const value_type p = *left;
271  const value_type q = *(left + 1);
272  const value_type r = *(right - 1);
273
274  while (j <= k) {
275  while (cmp(*j, q)) {
276  if (cmp(*j, p)) {
277  swap(*i, *j);
278  i++;
279  }
280  j++;
281  }
282
283  while (cmp(q, *k)) {
284  if (cmp(r, *k)) {
285  swap(*k, *l);
286  l--;
287  }
288  k--;
289  }
290
291  if (j <= k) {
292  if (cmp(r, *j)) {
293  if (cmp(*k, p)) {
294  qsort_local::rotate4(*j, *i, *k, *l);
295  i++;
296  }
297  else {
298  qsort_local::rotate3(*j, *k, *l);
299  }
300  l--;
301  }
302  else {
303  if (cmp(*k, p)) {
304  qsort_local::rotate3(*j, *i, *k);
305  i++;
306  }
307  else {
308  swap(*j, *k);
309  }
310  }
311  j++, k--;
312  }
313  }
314
315  qsort_local::rotate3(*(left + 1), *(i - 1), *(j - 1));
316
317  swap(*left, *(i - 2));
318  swap(*(right - 1), *(l + 1));
319
320  sLOG0 << "qsort_three_pivots: "
321  << i - 2 - left
322  << j - i
323  << l + 1 - j
324  << right - l - 2;
325
326  qsort_three_pivots<Compare>(left, i - 2, cmp);
327  qsort_three_pivots<Compare>(i - 1, j - 1, cmp);
328  qsort_three_pivots<Compare>(j, l + 1, cmp);
329  qsort_three_pivots<Compare>(l + 2, right, cmp);
330 }
331
332 } // namespace common
333 } // namespace thrill
334
336
337 /******************************************************************************/
void rotate3(ValueType &a0, ValueType &a1, ValueType &a2)
Assigns a0 <- a1, a1 <- a2, and a2 <- a0.
Definition: qsort.hpp:32
void InsertionSort(Iterator left, Iterator right, Compare cmp)
Definition: qsort.hpp:113
void qsort_three_pivots(Iterator left, Iterator right, Compare cmp)
Definition: qsort.hpp:244
void qsort_two_pivots_yaroslavskiy(Iterator lo, Iterator hi, Compare cmp)
Definition: qsort.hpp:186
void sort3(Iterator x, Iterator y, Iterator z, Compare cmp)
Sort three items, stable, 2-3 compares, 0-2 swaps.
Definition: qsort.hpp:51
void rotate4(ValueType &a0, ValueType &a1, ValueType &a2, ValueType &a3)
Assigns a0 <- a1, a1 <- a2, a2 <- a3, and a3 <- a0.
Definition: qsort.hpp:41
#define sLOG0
Override default output: never or always output log.
Definition: logger.hpp:37
void sort_samples(Iterator *A, size_t size, Compare cmp)
Sort iterators by their content, used for sorting pivot samples.
Definition: qsort.hpp:166
Iterator median3(Iterator a, Iterator b, Iterator c, Compare cmp)
Definition: qsort.hpp:145
void sort4(Iterator x1, Iterator x2, Iterator x3, Iterator x4, Compare cmp)
Sort four items, stable, 3-6 compares, 0-5 swaps.
Definition: qsort.hpp:76
void swap(CountingPtr< A, D > &a1, CountingPtr< A, D > &a2) noexcept
list x
Definition: gen_data.py:39
void sort5(Iterator x1, Iterator x2, Iterator x3, Iterator x4, Iterator x5, Compare cmp)
Sort five items, 4-10 compares, 0-9 swaps.
Definition: qsort.hpp:93