1// a sorting example that uses the worst-case for conventional MSD radix sorts.
2//
3// Copyright Steven Ross 2009-2014.
4//
5// Distributed under the Boost Software License, Version 1.0.
6// (See accompanying file LICENSE_1_0.txt or copy at
7// http://www.boost.org/LICENSE_1_0.txt)
8
9// See http://www.boost.org/libs/sort for library home page.
10
11#include <boost/sort/spreadsort/spreadsort.hpp>
12#include <time.h>
13#include <stdio.h>
14#include <stdlib.h>
15#include <algorithm>
16#include <vector>
17#include <string>
18#include <fstream>
19#include <sstream>
20#include <iostream>
21using namespace boost::sort::spreadsort;
22using namespace std;
23
24#define DATA_TYPE boost::uint64_t
25
26#define ALR_THRESHOLD 3
27
28const unsigned max_count = ALR_THRESHOLD - 1;
29const unsigned bit_shift = detail::rough_log_2_size(input: max_count) -
30 detail::int_log_mean_bin_size;
31const unsigned radix_threshold = detail::rough_log_2_size(input: max_count) + 1;
32//Increase this size if too fast to test accurately
33const unsigned top_splits = 12;
34
35const DATA_TYPE typed_one = 1;
36
37void
38fill_vector(vector<DATA_TYPE> & input, const DATA_TYPE base_value,
39 unsigned remaining_bits)
40{
41 if (remaining_bits >= radix_threshold) {
42 input.push_back(x: (base_value << remaining_bits) +
43 ((typed_one << remaining_bits) - 1));
44 fill_vector(input, base_value: base_value << bit_shift, remaining_bits: remaining_bits - bit_shift);
45 }
46 else {
47 for (unsigned u = 0; u < max_count; ++u)
48 input.push_back(x: (base_value << remaining_bits) +
49 (rand() % (1 << remaining_bits)));
50 }
51}
52
53//Tests spreadsort on the worst-case distribution for standard MSD radix sorts.
54int main(int, const char **) {
55 vector<DATA_TYPE> input;
56 for (int ii = (1 << top_splits) - 1; ii >= 0; --ii)
57 fill_vector(input, base_value: ii, remaining_bits: (sizeof(DATA_TYPE) * 8) - top_splits);
58
59 //Run both std::sort and spreadsort
60 for (unsigned u = 0; u < 2; ++u) {
61 vector<DATA_TYPE> array = input;
62 clock_t start, end;
63 double elapsed;
64 start = clock();
65 if (u)
66 std::sort(first: array.begin(), last: array.end());
67 else
68 boost::sort::spreadsort::spreadsort(first: array.begin(), last: array.end());
69 end = clock();
70 elapsed = static_cast<double>(end - start);
71 if (u)
72 printf(format: "std::sort elapsed time %f\n", elapsed / CLOCKS_PER_SEC);
73 else
74 printf(format: "spreadsort elapsed time %f\n", elapsed / CLOCKS_PER_SEC);
75 array.clear();
76 }
77 return 0;
78}
79

source code of boost/libs/sort/example/alrbreaker.cpp