Sorting algorithms/Strand sort: Difference between revisions
Content added Content deleted
(Add Nimrod) |
(jq) |
||
Line 595: | Line 595: | ||
[1, 2, 3, 3, 4, 5] |
[1, 2, 3, 3, 4, 5] |
||
[1, 2, 3, 3, 3, 4, 5, 6]</pre> |
[1, 2, 3, 3, 3, 4, 5, 6]</pre> |
||
=={{header|jq}}== |
|||
Most of the implementation is the "merge" function for merging two arrays. Notice that the helper function, strand, is defined here as an inner function.<lang jq># merge input array with array x by comparing the heads of the arrays |
|||
# in turn; # if both arrays are sorted, the result will be sorted: |
|||
def merge(x): |
|||
length as $length |
|||
| (x|length) as $xl |
|||
| if $length == 0 then x |
|||
elif $xl == 0 then . |
|||
else |
|||
. as $in |
|||
| reduce range(0; $xl + $length) as $z |
|||
# state [ix, xix, ans] |
|||
( [0, 0, []]; |
|||
if .[0] < $length and |
|||
((.[1] < $xl and $in[.[0]] <= x[.[1]]) or .[1] == $xl) |
|||
then [(.[0] + 1), .[1], (.[2] + [$in[.[0]]]) ] |
|||
else [.[0], (.[1] + 1), (.[2] + [x[.[1]]]) ] |
|||
end |
|||
) | .[2] |
|||
end ; |
|||
def strand_sort: |
|||
# The inner function emits [strand, remainder] |
|||
def strand: |
|||
if length <= 1 then . |
|||
else |
|||
reduce .[] as $x |
|||
# state: [strand, remainder] |
|||
([ [], [] ]; |
|||
if ((.[0]|length) == 0) or .[0][-1] <= $x |
|||
then [ (.[0] + [$x]), .[1] ] |
|||
else [ .[0], (.[1] + [$x]) ] |
|||
end ) |
|||
end ; |
|||
if length <= 1 then . |
|||
else strand as $s |
|||
| ($s[0] | merge( $s[1] | strand_sort)) |
|||
end ; |
|||
</lang> |
|||
Example: |
|||
[1,3,5,2,4,6] | strand_sort |
|||
=={{header|Mathematica}}== |
=={{header|Mathematica}}== |