Anonymous user
Sorting algorithms/Cycle sort: Difference between revisions
Added Ruby
(Add C) |
(Added Ruby) |
||
Line 933:
.swap: do p=p while x==@.p; end; parse value @.p x with x @.p;w=w+1;return</lang>
'''output''' is identical to the 2<sup>nd</sup> version.
=={{header|Ruby}}==
Direct translation of the pseudocode on the Wikipedia.
<lang ruby>def cycleSort!(array)
writes = 0
# Loop through the array to find cycles to rotate.
for cycleStart in 0 .. array.size-2
item = array[cycleStart]
# Find where to put the item.
pos = cycleStart
for i in cycleStart+1 ... array.size
pos += 1 if array[i] < item
end
# If the item is already there, this is not a cycle.
next if pos == cycleStart
# Otherwise, put the item there or right after any duplicates.
pos += 1 while item == array[pos]
array[pos], item = item, array[pos]
writes += 1
# Rotate the rest of the cycle.
while pos != cycleStart
# Find where to put the item.
pos = cycleStart
for i in cycleStart+1 ... array.size
pos += 1 if array[i] < item
end
# Put the item there or right after any duplicates.
pos += 1 while item == array[pos]
array[pos], item = item, array[pos]
writes += 1
end
end
writes
end
p a = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
puts "writes : #{cycleSort!(a)}"
p a</lang>
{{out}}
<pre>
[0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]
writes : 10
[0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9]
</pre>
=={{header|Scala}}==
| |||