Anonymous user
Sorting Algorithms/Circle Sort: Difference between revisions
J solution
(→{{header|Python}}: this version actually works.) |
(J solution) |
||
Line 210:
sample /sample sort .sample</lang>
=={{header|J}}==
Of more parsing and atomic data, or less parsing with large data groups the latter produces faster J programs. Consequently each iteration laminates the original with its reverse. It joins the recursive call to the pairwise minima of the left block to the recursive call of the pairwise maxima of the right block, repeating the operations while the output changes. This is sufficient for power of 2 length data. The pre verb adjusts the data length. And post recovers the original data. This implementation discards the "in place" property described at the sourceforge link.
<lang J>
circle_sort =: post ([: power_of_2_length pre) NB. the main sorting verb
power_of_2_length =: even_length_iteration^:_ NB. repeat while the answer changes
even_length_iteration =: ((,: |.) (([: <./ ({.~ _&,)) ,&$: ([: >./ (}.~ 0&,))) (1r2 * #))^:(1 < #)
pre =: , (([: (-~ >.&.(2&^.)) #) # >./) NB. extend data to next power of 2 length
post =: ({.~ #)~ NB. remove the extra data
</lang>
Examples:
<lang J>
show =: [ smoutput
8 ([: circle_sort&.>@show ;&(?~)) 13 NB. sort lists length 8 and 13
┌───────────────┬────────────────────────────┐
│0 6 7 3 4 5 2 1│3 10 1 4 7 8 5 6 2 0 9 11 12│
└───────────────┴────────────────────────────┘
┌───────────────┬────────────────────────────┐
│0 1 2 3 4 5 6 7│0 1 2 3 4 5 6 7 8 9 10 11 12│
└───────────────┴────────────────────────────┘
8 ([: circle_sort&.>@show ;&(1 }. 2 # ?~)) 13 NB. data has repetition
┌─────────────────────────────┬──────────────────────────────────────────────────────┐
│2 3 3 5 5 1 1 7 7 6 6 4 4 0 0│12 11 11 4 4 3 3 9 9 7 7 10 10 6 6 2 2 1 1 5 5 8 8 0 0│
└─────────────────────────────┴──────────────────────────────────────────────────────┘
┌─────────────────────────────┬──────────────────────────────────────────────────────┐
│0 0 1 1 2 3 3 4 4 5 5 6 6 7 7│0 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 11 12│
└─────────────────────────────┴──────────────────────────────────────────────────────┘
</lang>
=={{header|Python}}==
The doctest passes with odd and even length lists. As do the random tests. Please see circle_sort.__doc__ for example use and output.
<lang python>
#python3
| |||