Sorting algorithms/Cycle sort: Difference between revisions
Content added Content deleted
m (→{{header|Phix}}: added syntax colouring the hard way) |
|||
Line 998: | Line 998: | ||
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z] |
[a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, r, s, t, u, v, w, x, y, z] |
||
</pre> |
</pre> |
||
=={{header|Lua}}== |
|||
{{trans|Java}} |
|||
<lang lua>function printa(a) |
|||
io.write("[") |
|||
for i,v in ipairs(a) do |
|||
if i > 1 then |
|||
io.write(", ") |
|||
end |
|||
io.write(v) |
|||
end |
|||
io.write("]") |
|||
end |
|||
function cycle_sort(a) |
|||
local writes = 0 |
|||
local cycle_start = 0 |
|||
while cycle_start < #a - 1 do |
|||
local val = a[cycle_start + 1] |
|||
-- count the number of values that are smaller than val since cycle_start |
|||
local pos = cycle_start |
|||
local i = cycle_start + 1 |
|||
while i < #a do |
|||
if a[i + 1] < val then |
|||
pos = pos + 1 |
|||
end |
|||
i = i + 1 |
|||
end |
|||
-- there aren't any |
|||
if pos ~= cycle_start then |
|||
-- skip duplicates |
|||
while val == a[pos + 1] do |
|||
pos = pos + 1 |
|||
end |
|||
-- put val in final position |
|||
a[pos + 1], val = val, a[pos + 1] |
|||
writes = writes + 1 |
|||
-- repeat as long as we can find values to swap |
|||
-- otherwise start new cycle |
|||
while pos ~= cycle_start do |
|||
pos = cycle_start |
|||
local i = cycle_start + 1 |
|||
while i < #a do |
|||
if a[i + 1] < val then |
|||
pos = pos + 1 |
|||
end |
|||
i = i + 1 |
|||
end |
|||
while val == a[pos + 1] do |
|||
pos = pos + 1 |
|||
end |
|||
a[pos + 1], val = val, a[pos + 1] |
|||
writes = writes + 1 |
|||
end |
|||
end |
|||
cycle_start = cycle_start + 1 |
|||
end |
|||
return writes |
|||
end |
|||
arr = {5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1} |
|||
printa(arr) |
|||
print() |
|||
writes = cycle_sort(arr) |
|||
printa(arr) |
|||
print() |
|||
print("writes: " .. writes)</lang> |
|||
{{out}} |
|||
<pre>[5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1] |
|||
[0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 5, 5, 5, 6, 8, 9] |
|||
writes: 14</pre> |
|||
=={{header|NetRexx}}== |
=={{header|NetRexx}}== |