Sorting algorithms/Strand sort: Difference between revisions

Content added Content deleted
(Small improvements in second D entry)
Line 281: Line 281:


=== Faster version using slices ===
=== Faster version using slices ===
<lang d>import std.stdio, std.range;
<lang d>import std.stdio, std.array;


T[] strandSort(T)(T[] list) {
T[] strandSort(T)(/*in*/ T[] list) pure nothrow {
T[] merge(T[] left, T[] right) {
static T[] merge(T[] left, T[] right) pure nothrow {
T[] res;
T[] result;
while (!left.empty && !right.empty) {
while (!left.empty && !right.empty) {
if (left.front <= right.front) {
if (left.front <= right.front) {
res ~= left.front;
result ~= left.front;
left = left[1 .. $];
left.popFront;
} else {
} else {
res ~= right.front;
result ~= right.front;
right = right[1 .. $];
right.popFront;
}
}
}
}
return res ~ left ~ right;
return result ~ left ~ right;
}
}


T[] result, sorted, leftover;
T[] result;
while (!list.empty) {
while (!list.empty) {
leftover = [];
auto sorted = list[0 .. 1];
sorted = [list.front];
list.popFront;
list = list[1 .. $];
T[] leftover;
foreach (item; list) {
foreach (item; list)
if (sorted.back <= item) {
(sorted.back <= item ? sorted : leftover) ~= item;
sorted ~= item;
} else {
leftover ~= item;
}
}
result = merge(sorted, result);
result = merge(sorted, result);
list = leftover;
list = leftover;
}
}

return result;
return result;
}
}
Line 318: Line 314:
void main() {
void main() {
auto arr = [-2,0,-2,5,5,3,-1,-3,5,5,0,2,-4,4,2];
auto arr = [-2,0,-2,5,5,3,-1,-3,5,5,0,2,-4,4,2];
arr.strandSort.writeln;
foreach (e; strandSort(arr))
write(e, " ");
}</lang>
}</lang>
{{out}}
{{out}}
<pre>-4 -3 -2 -2 -1 0 0 2 2 3 4 5 5 5 5 </pre>
<pre>[-4, -3, -2, -2, -1, 0, 0, 2, 2, 3, 4, 5, 5, 5, 5]</pre>


=={{header|Euphoria}}==
=={{header|Euphoria}}==
Retrieved from "https://rosettacode.org/wiki/Sorting_algorithms/Strand_sort"