Sorting Algorithms/Circle Sort: Difference between revisions
→{{header|Phix}}
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: fixed output error) |
|||
Line 1,029:
The brown fox jumps lazy dog. quick over the
The brown dog. fox jumps lazy over quick the</pre>
=={{header|Phix}}==
<lang Phix>sequence array
function circle_sort_inner(integer lo, hi, swaps, level=1)
if lo!=hi then
integer high := hi,
low := lo,
mid := floor((high-low)/2)
while lo <= hi do
hi += (lo=hi)
if array[lo] > array[hi] then
{array[lo],array[hi]} = {array[hi],array[lo]}
?{array,"level",level,{low,high}}
swaps += 1
end if
lo += 1
hi -= 1
end while
swaps = circle_sort_inner(low,low+mid,swaps,level+1)
swaps = circle_sort_inner(low+mid+1,high,swaps,level+1)
end if
return swaps
end function
procedure circle_sort()
?{array,"<== (initial)"}
while circle_sort_inner(1, length(array), 0) do ?"loop" end while
?{array,"<== (sorted)"}
end procedure
array = {5, -1, 101, -4, 0, 1, 8, 6, 2, 3}
--array = {-4,-1,1,0,5,-7,-2,4,-6,-3,2,6,3,7,-5}
--array = {6, 7, 8, 9, 2, 5, 3, 4, 1}
--array = {2,14,4,6,8,1,3,5,7,9,10,11,0,13,12,-1}
--array = {"the","quick","brown","fox","jumps","over","the","lazy","dog"}
--array = {0.603704, 0.293639, 0.513965, 0.746246, 0.245282, 0.930508, 0.550878, 0.622534, 0.006089, 0.270426}
--array = shuffle(array)
circle_sort()</lang>
{{out}}
Shows the full inner workings: call depth and range being considered, after each swap made.
<pre>
{{5,-1,101,-4,0,1,8,6,2,3},"<== (initial)"}
{{3,-1,101,-4,0,1,8,6,2,5},"level",1,{1,10}}
{{3,-1,6,-4,0,1,8,101,2,5},"level",1,{1,10}}
{{0,-1,6,-4,3,1,8,101,2,5},"level",2,{1,5}}
{{0,-4,6,-1,3,1,8,101,2,5},"level",2,{1,5}}
{{0,-4,-1,6,3,1,8,101,2,5},"level",2,{1,5}}
{{-1,-4,0,6,3,1,8,101,2,5},"level",3,{1,3}}
{{-4,-1,0,6,3,1,8,101,2,5},"level",4,{1,2}}
{{-4,-1,0,3,6,1,8,101,2,5},"level",3,{4,5}}
{{-4,-1,0,3,6,1,2,101,8,5},"level",2,{6,10}}
{{-4,-1,0,3,6,1,2,8,101,5},"level",2,{6,10}}
{{-4,-1,0,3,6,1,2,8,5,101},"level",3,{9,10}}
"loop"
{{-4,-1,0,2,6,1,3,8,5,101},"level",1,{1,10}}
{{-4,-1,0,2,1,6,3,8,5,101},"level",1,{1,10}}
{{-4,-1,0,1,2,6,3,8,5,101},"level",3,{4,5}}
{{-4,-1,0,1,2,6,3,5,8,101},"level",2,{6,10}}
{{-4,-1,0,1,2,5,3,6,8,101},"level",3,{6,8}}
{{-4,-1,0,1,2,3,5,6,8,101},"level",4,{6,7}}
"loop"
{{-4,-1,0,1,2,3,5,6,8,101},"<== (sorted)"}
</pre>
=={{header|Python}}==
| |||