Sorting algorithms/Strand sort: Difference between revisions
Content added Content deleted
(→Faster version using slices: we're already using the identifier "result" in the enclosing function, better not use it also in the nested function, "res" is clear enough) |
(Updated second D entry) |
||
Line 283: | Line 283: | ||
<lang d>import std.stdio, std.array; |
<lang d>import std.stdio, std.array; |
||
T[] strandSort(T)( |
T[] strandSort(T)(const(T)[] list) pure nothrow { |
||
static T[] merge(T[] left, T[] right) pure nothrow { |
static T[] merge(const(T)[] left, const(T)[] right) pure nothrow { |
||
T[] res; |
T[] res; |
||
while (!left.empty && !right.empty) { |
while (!left.empty && !right.empty) { |
||
Line 302: | Line 302: | ||
auto sorted = list[0 .. 1]; |
auto sorted = list[0 .. 1]; |
||
list.popFront; |
list.popFront; |
||
typeof(sorted) leftover; |
|||
foreach (item; list) |
foreach (const item; list) |
||
(sorted.back <= item ? sorted : leftover) ~= item; |
(sorted.back <= item ? sorted : leftover) ~= item; |
||
result = merge(sorted, result); |
result = merge(sorted, result); |
||
Line 313: | Line 313: | ||
void main() { |
void main() { |
||
const arr = [-2, 0, -2, 5, 5, 3, -1, -3, 5, 5, 0, 2, -4, 4, 2]; |
|||
arr.strandSort.writeln; |
arr.strandSort.writeln; |
||
}</lang> |
}</lang> |