1 /** Fixed Length Sorting via Sorting Networks. 2 3 See_Also: http://forum.dlang.org/post/ne5m62$1gu5$1@digitalmars.com 4 See_Also: http://cpansearch.perl.org/src/JGAMBLE/Algorithm-Networksort-1.30/lib/Algorithm/Networksort.pm 5 See_Also: http://www.angelfire.com/blog/ronz/Articles/999SortingNetworksReferen.html 6 7 License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0). 8 9 TODO see some sizes are not supported, we should not have holes. 10 Use http://www.angelfire.com/blog/ronz/Articles/999SortingNetworksReferen.html 11 12 TODO Sometimes the sort routine gets too bulky. Suggestion: also define 13 networks for `medianOfUpTo` and `medianExactly`, then use them in a 14 quicksort manner - first compute the median to segregate values in 15 below/over the median, then make two calls to `sortExactly!(n / 2)`. That 16 way you get to sort n values with median of n values (smaller and simpler) 17 and two sorts of n / 2 values. 18 19 TODO Stability of equal elements: Need template parameter `equalityStability`? Scalar builtin values are always stable. 20 21 TODO There should be a notion of at what point the networks become too bulky 22 to be fast - 6-16 may be the limit. 23 24 TODO There is a nice peephole optimization you could make. Consider: 25 26 r.conditionalSwap!("a < b", less, 0, 1, 1, 2)(r); 27 28 which needs to do 29 30 if (r[1] < r[0]) r.swapAt(0, 1); 31 if (r[2] < r[1]) r.swapAt(1, 2); 32 33 For types with no elaborate copy/assignment, it's more efficient to use a 34 "hole"-based approach - assign the first element to a temporary and then 35 consider it a hole that you fill, then leaving another hole: 36 37 if (r[1] < r[0]) 38 if (r[2] < r[0]) r.swapAt(0, 1, 2); 39 else r.swapAt(0, 1); 40 else 41 if (r[2] < r[1]) r.swapAt(1, 2); 42 43 with swapAt with three argument having this definition: 44 45 auto t = r[a]; r[a] = r[b]; r[b] = r[c]; r[c] = t; 46 47 i.e. create a temporary (which creates a "hole" in the array) then fill it 48 leaving another hole etc., until the last hole is filled with the temporary. 49 */ 50 module nxt.sortn; 51 52 import std.meta : allSatisfy; 53 import std.traits : isIntegral; 54 import std.range.primitives : isRandomAccessRange; 55 56 /** Static Iota. 57 TODO Move to Phobos std.range. 58 */ 59 template iota(size_t from, size_t to) 60 if (from <= to) 61 { 62 alias iota = iotaImpl!(to - 1, from); 63 } 64 private template iotaImpl(size_t to, size_t now) 65 { 66 import std.meta : AliasSeq; 67 static if (now >= to) { alias iotaImpl = AliasSeq!(now); } 68 else { alias iotaImpl = AliasSeq!(now, iotaImpl!(to, now + 1)); } 69 } 70 71 /** Conditionally pairwise sort elements of `Range` `r` at `indexes` using 72 comparison predicate `less`. 73 74 TODO Perhaps defines as 75 76 template conditionalSwap(indexes...) 77 { 78 void conditionalSwap(less = "a < b", Range)(Range r) 79 { 80 } 81 } 82 83 instead. 84 */ 85 void conditionalSwap(alias less = "a < b", Range, indexes...)(Range r) 86 if (isRandomAccessRange!Range && 87 allSatisfy!(isIntegral, typeof(indexes)) && 88 indexes.length && 89 (indexes.length & 1) == 0) // even number of indexes 90 { 91 import std.algorithm.mutation : swapAt; 92 import std.functional : binaryFun; 93 import nxt.static_iota : iota; 94 foreach (const i; iota!(0, indexes.length / 2)) 95 { 96 const j = indexes[2*i]; 97 const k = indexes[2*i + 1]; 98 99 static assert(j >= 0, "First part of index pair " ~ i.stringof ~ " is negative"); 100 static assert(k >= 0, "Second part of index pair " ~ i.stringof ~ " is negative"); 101 102 if (!binaryFun!less(r[j], r[k])) 103 { 104 r.swapAt(j, k); 105 } 106 } 107 } 108 109 /** Largest length supported by network sort `networkSortUpTo`. */ 110 enum networkSortMaxLength = 22; 111 112 /** Sort at most the first `n` elements of `r` using comparison `less` using 113 * a networking sort. 114 * 115 * Note: Sorting networks are not unique, not even optimal solutions. 116 * 117 * See_Also: http://stackoverflow.com/questions/3903086/standard-sorting-networks-for-small-values-of-n 118 * See_Also: http://www.cs.brandeis.edu/~hugues/sorting_networks.html 119 */ 120 auto networkSortUpTo(uint n, alias less = "a < b", Range)(Range r) 121 if (n >= 2 && 122 isRandomAccessRange!Range) 123 in 124 { 125 assert(r.length >= n); 126 } 127 do 128 { 129 auto s = r[0 .. n]; 130 131 static if (n < 2) 132 { 133 return; // no sorting needed 134 } 135 136 static if (n == 2) 137 { 138 s.conditionalSwap!(less, Range, 0, 1); 139 } 140 else static if (n == 3) 141 { 142 s.conditionalSwap!(less, Range, 143 0,1, 144 1,2, 145 0,1); 146 } 147 else static if (n == 4) 148 { 149 s.conditionalSwap!(less, Range, 150 0,1, 2,3, // 2 in parallel 151 0,2, 1,3, // 2 in parallel 152 1,2); 153 } 154 else static if (n == 5) 155 { 156 s.conditionalSwap!(less, Range, 157 0,1, 3,4, // 2 in parallel 158 0,2, 159 0,3, 1,2, // 2 in parallel 160 2,3, 1,4, // 2 in parallel 161 1,2, 3,4); // 2 in parallel 162 } 163 else static if (n == 6) 164 { 165 s.conditionalSwap!(less, Range, 166 0,1, 2,3, 4,5, // 3 in parallel 167 0,2, 1,4, 3,5, // 3 in parallel 168 0,1, 2,3, 4,5, // 3 in parallel 169 1,2, 3,4, // 2 in parallel 170 2,3); 171 } 172 else static if (n == 8) // Bitonic Sorter. 6-steps: https://en.wikipedia.org/wiki/Bitonic_sorter 173 { 174 s.conditionalSwap!(less, Range, 175 0,1, 2,3, 4,5, 6,7, 176 0,3, 4,7, 1,2, 5,6, 177 0,1, 2,3, 4,5, 6,7, 178 0,7, 1,6, 2,5, 3,4, 179 0,2, 1,3, 4,6, 5,7, 180 0,1, 2,3, 4,5, 6,7); 181 } 182 else static if (n == 9) // R. W. Floyd. 183 { 184 s.conditionalSwap!(less, Range, 185 0,1, 3,4, 6,7, 186 1,2, 4,5, 7,8, 187 0,1, 3,4, 6,7, 188 0,3, 189 3,6, 190 0,3, 1,4, 191 4,7, 192 1,4, 2,5, 193 5,8, 194 1,3, 2,5, 195 2,6, 5,7, 196 4,6, 197 2,4, 198 2,3, 5,6); 199 } 200 else static if (n == 10) // A. Waksman. 201 { 202 s.conditionalSwap!(less, Range, 203 0,5, 1,6, 2,7, 3,8, 4,9, 204 0,3, 1,4, 5,8, 6,9, 205 0,2, 3,6, 7,9, 206 0,1, 2,4, 5,7, 8,9, 207 1,2, 3,5, 4,6, 7,8, 208 1,3, 2,5, 4,7, 6,8, 209 2,3, 6,7, 210 3,4, 5,6, 211 4,5); 212 } 213 else static if (n == 11) // 12-input by Shapiro and Green, minus the connections to a twelfth input. 214 { 215 s.conditionalSwap!(less, Range, 216 0,1, 2,3, 4,5, 6,7, 8,9, 217 0,2, 1,3, 4,6, 5,7, 8,10, 218 1,2, 5,6, 9,10, 219 1,5, 6,10, 220 2,6, 5,9, 221 0,4, 1,5, 6,10, 222 3,7, 4,8, 223 0,4, 224 1,4, 3,8, 7,10, 225 2,3, 8,9, 226 2,4, 3,5, 6,8, 7,9, 227 3,4, 5,6, 7,8); 228 } 229 else static if (n == 12) // Shapiro and Green. 230 { 231 s.conditionalSwap!(less, Range, 232 0,1, 2,3, 4,5, 6,7, 8,9, 10,11, 233 0,2, 1,3, 4,6, 5,7, 9,11, 8,10, 234 1,2, 5,6, 9,10, 235 1,5, 6,10, 236 2,6, 5,9, 237 0,4, 1,5, 6,10, 7,11, 238 3,7, 4,8, 239 0,4, 7,11, 240 1,4, 3,8, 7,10, 241 2,3, 8,9, 242 2,4, 3,5, 6,8, 7,9, 243 3,4, 5,6, 7,8); 244 } 245 else static if (n == 13) // Generated by the END algorithm. 246 { 247 s.conditionalSwap!(less, Range, 248 0,12, 1,7, 2,6, 3,4, 5,8, 9,11, 249 0,1, 2,3, 4,6, 5,9, 7,12, 8,11, 250 0,2, 1,4, 3,7, 6,12, 7,8, 10,11, 251 4,9, 6,10, 11,12, 252 1,7, 3,4, 5,6, 8,9, 10,11, 253 1,3, 2,6, 4,7, 8,10, 9,11, 254 0,5, 2,5, 6,8, 9,10, 255 1,2, 3,5, 4,6, 7,8, 256 2,3, 4,5, 6,7, 8,9, 257 3,4, 5,6); 258 } 259 else static if (n == 14) // Green's construction for 16 inputs minus connections to the fifteenth and sixteenth inputs. 260 { 261 s.conditionalSwap!(less, Range, 262 0,1, 2,3, 4,5, 6,7, 8,9, 10,11, 12,13, 263 0,2, 1,3, 4,6, 5,7, 8,10, 9,11, 264 0,4, 1,5, 2,6, 3,7, 8,12, 9,13, 265 0,8, 1,9, 2,10, 3,11, 4,12, 5,13, 266 3,12, 5,10, 6,9, 267 1,2, 4,8, 7,11, 268 1,4, 2,8, 7,13, 269 2,4, 3,8, 5,6, 7,12, 9,10, 11,13, 270 3,5, 6,8, 7,9, 10,12, 271 3,4, 5,6, 7,8, 9,10, 11,12, 272 6,7, 8,9); 273 } 274 else static if (n == 15) // Green's construction for 16 inputs minus connections to the sixteenth input. 275 { 276 s.conditionalSwap!(less, Range, 277 0,1, 2,3, 4,5, 6,7, 8,9, 10,11, 12,13, 278 0,2, 1,3, 4,6, 5,7, 8,10, 9,11, 12,14, 279 0,4, 1,5, 2,6, 3,7, 8,12, 9,13, 10,14, 280 0,8, 1,9, 2,10, 3,11, 4,12, 5,13, 6,14, 281 3,12, 5,10, 6,9, 13,14, 282 1,2, 4,8, 7,11, 283 1,4, 2,8, 7,13, 11,14, 284 2,4, 3,8, 5,6, 7,12, 9,10, 11,13, 285 3,5, 6,8, 7,9, 10,12, 286 3,4, 5,6, 7,8, 9,10, 11,12, 287 6,7, 8,9); 288 } 289 else static if (n == 16) // Green's construction. TODO Use 10-step Bitonic sorter instead? 290 { 291 s.conditionalSwap!(less, Range, 292 0,1, 2,3, 4,5, 6,7, 8,9, 10,11, 12,13, 14,15, 293 0,2, 1,3, 4,6, 5,7, 8,10, 9,11, 12,14, 13,15, 294 0,4, 1,5, 2,6, 3,7, 8,12, 9,13, 10,14, 11,15, 295 0,8, 1,9, 2,10, 3,11, 4,12, 5,13, 6,14, 7,15, 296 3,12, 5,10, 6,9, 13,14, 297 1,2, 4,8, 7,11, 298 1,4, 2,8, 7,13, 11,14, 299 2,4, 3,8, 5,6, 7,12, 9,10, 11,13, 300 3,5, 6,8, 7,9, 10,12, 301 3,4, 5,6, 7,8, 9,10, 11,12, 302 6,7, 8,9); 303 } 304 else static if (n == 18) // Baddar's PHD thesis, chapter 6. Fewest stages but 2 comparators more than 'batcher' 305 { 306 s.conditionalSwap!(less, Range, 307 0,1, 2,3, 4,5, 6,7, 8,9, 10,11, 12,13, 14,15, 16,17, 308 0,2, 1,3, 4,6, 5,7, 8,10, 9,11, 12,17, 13,14, 15,16, 309 0,4, 1,5, 2,6, 3,7, 9,10, 8,12, 11,16, 13,15, 14,17, 310 0,8, 1,13, 2,4, 3,5, 6,17, 7,16, 9,15, 10,14, 11,12, 311 0,1, 2,11, 3,15, 4,10, 5,12, 6,13, 7,14, 8,9, 16,17, 312 1,8, 3,10, 4,15, 5,11, 6,9, 7,13, 14,16, 313 1,2, 3,6, 4,8, 5,9, 7,11, 10,13, 12,16, 14,15, 314 2,3, 5,8, 6,7, 9,10, 11,14, 12,13, 315 2,4, 3,5, 6,8, 7,9, 10,11, 12,14, 13,15, 316 3,4, 5,6, 7,8, 9,10, 11,12, 13,14, 317 4,5, 6,7, 8,9, 10,11, 12,13); 318 } 319 else static if (n == 22) // Baddar's PHD thesis, chapter 7. Fewest stages but 2 comparators more than 'batcher' 320 { 321 s.conditionalSwap!(less, Range, 322 0,1, 2,3, 4,5, 6,7, 8,9, 10,11, 12,13, 14,15, 16,17, 18,19, 20,21, 323 0,5, 1,3, 2,4, 6,8, 7,9, 10,12, 11,13, 14,16, 15,17, 18,20, 19,21, 324 6,10, 7,11, 8,12, 9,13, 14,18, 15,19, 16,20, 17,21, 325 0,2, 1,4, 3,5, 7,15, 8,16, 9,17, 11,19, 326 0,10, 1,18, 3,12, 5,20, 13,21, 327 0,7, 2,4, 3,15, 6,14, 9,18, 17,20, 328 0,6, 1,8, 2,11, 3,8, 4,16, 5,10, 12,19, 13,14, 20,21, 329 2,13, 4,7, 5,9, 10,15, 11,17, 12,18, 14,16, 16,20, 18,19, 330 1,3, 2,6, 4,5, 7,9, 8,13, 10,11, 12,14, 15,17, 19,20, 331 3,5, 4,6, 7,8, 9,13, 10,12, 11,14, 15,18, 16,17, 332 1,2, 5,10, 6,7, 8,9, 11,12, 13,15, 14,16, 18,19, 333 2,3, 5,7, 8,10, 9,11, 12,13, 14,15, 16,18, 17,19, 334 2,4, 3,6, 7,8, 9,10, 11,12, 13,14, 15,16, 17,18, 335 3,4, 5,6, 8,9, 10,11, 12,13, 14,15, 16,17, 336 4,5, 6,7); 337 } 338 else 339 { 340 static assert(0, "Unsupported length: " ~ n.stringof); 341 } 342 343 import std.range : assumeSorted; 344 return s.assumeSorted!less; 345 } 346 347 /** Sort range `x` of length `n` using a networking sort. 348 */ 349 auto networkSortExactly(uint n, alias less = "a < b", Range)(Range r) 350 if (n >= 2 && 351 isRandomAccessRange!Range) 352 in 353 { 354 assert(r.length == n); 355 } 356 do 357 { 358 x[].networkSortUpTo!(n); 359 } 360 361 /** Sort static array `x` of length `n` using a networking sort. 362 */ 363 auto networkSortExactly(alias less = "a < b", T, size_t n)(ref T[n] x) 364 if (n >= 2) 365 { 366 x[].networkSortUpTo!(n); 367 } 368 369 /// 370 @safe pure nothrow @nogc unittest 371 { 372 import std.algorithm.comparison : equal; 373 int[4] x = [2, 3, 0, 1]; 374 const int[4] y = [0, 1, 2, 3]; 375 x.networkSortExactly; 376 assert(x[].equal(y[])); 377 } 378 379 /** Hybrid sort `r` using `networkSortUpTo` if length of `r` is 380 * less-than-or-equal to `networkSortMaxLength` and `std.algorithm.sorting.sort` 381 * otherwise. 382 */ 383 auto hybridSort(alias less = "a < b", Range)(Range r) 384 if (isRandomAccessRange!Range) 385 { 386 import std.algorithm.sorting : isSorted; 387 static foreach (n; 2 .. networkSortMaxLength + 1) 388 { 389 static if (__traits(compiles, { r.networkSortUpTo!(n, less); })) 390 { 391 if (n == r.length) 392 { 393 auto s = r.networkSortUpTo!(n, less); 394 assert(s.isSorted!less); 395 return s; 396 } 397 } 398 } 399 import std.algorithm.sorting : sort; 400 return sort!less(r); 401 } 402 403 /// 404 @safe pure unittest 405 { 406 import std.algorithm.sorting : isSorted; 407 import std.algorithm.iteration : permutations; 408 import std.range : iota; 409 import std.random : randomShuffle, Random; 410 411 Random random; 412 413 alias T = uint; 414 415 const maxFullPermutationTestLength = 8; 416 const maxTriedShufflings = 10_000; // maximum number of shufflings to try 417 418 import std.meta : AliasSeq; 419 foreach (less; AliasSeq!("a < b", "a > b")) 420 { 421 foreach (const n; 0 .. networkSortMaxLength + 1) 422 { 423 if (n > maxFullPermutationTestLength) // if number of elements is too large 424 { 425 foreach (x; 0 .. maxTriedShufflings) 426 { 427 import std.array : array; 428 auto y = iota(0, n).array; 429 y.randomShuffle(random); 430 y.hybridSort!less; 431 assert(y.isSorted!less); 432 } 433 } 434 else 435 { 436 foreach (x; iota(0, n).permutations) 437 { 438 import std.array : array; 439 auto y = x.array; 440 y.hybridSort!less; 441 assert(y.isSorted!less); 442 } 443 } 444 } 445 } 446 }