hybridSort

1 import std.algorithm.sorting : isSorted;
2 import std.algorithm.iteration : permutations;
3 import std.range : iota;
4 import std.random : randomShuffle, Random;
5 
6 Random random;
7 
8 alias T = uint;
9 
10 const maxFullPermutationTestLength = 8;
11 const maxTriedShufflings = 10_000; // maximum number of shufflings to try
12 
13 import std.meta : AliasSeq;
14 foreach (less; AliasSeq!("a < b", "a > b"))
15 {
16     foreach (const n; 0 .. networkSortMaxLength + 1)
17     {
18         if (n > maxFullPermutationTestLength) // if number of elements is too large
19         {
20             foreach (x; 0 .. maxTriedShufflings)
21             {
22                 import std.array : array;
23                 auto y = iota(0, n).array;
24                 y.randomShuffle(random);
25                 y.hybridSort!less;
26                 assert(y.isSorted!less);
27             }
28         }
29         else
30         {
31             foreach (x; iota(0, n).permutations)
32             {
33                 import std.array : array;
34                 auto y = x.array;
35                 y.hybridSort!less;
36                 assert(y.isSorted!less);
37             }
38         }
39     }
40 }