Sorting algorithms/Strand sort: Difference between revisions
Content deleted Content added
→Faster version using slices: missing imports |
Small improvements in second D entry |
||
Line 281: | Line 281: | ||
=== Faster version using slices === |
=== Faster version using slices === |
||
<lang d>import std.stdio, std. |
<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[] |
T[] result; |
||
while (!left.empty && !right.empty) { |
while (!left.empty && !right.empty) { |
||
if (left.front <= right.front) { |
if (left.front <= right.front) { |
||
result ~= left.front; |
|||
left |
left.popFront; |
||
} else { |
} else { |
||
result ~= right.front; |
|||
right |
right.popFront; |
||
} |
} |
||
} |
} |
||
return |
return result ~ left ~ right; |
||
} |
} |
||
T[] result |
T[] result; |
||
while (!list.empty) { |
while (!list.empty) { |
||
auto sorted = list[0 .. 1]; |
|||
list.popFront; |
|||
T[] leftover; |
|||
foreach (item; list) |
foreach (item; list) |
||
(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>[-4, -3, -2, -2, -1, 0, 0, 2, 2, 3, 4, 5, 5, 5, 5]</pre> |
||
=={{header|Euphoria}}== |
=={{header|Euphoria}}== |