Sorting algorithms/Cycle sort: Difference between revisions
Content added Content deleted
m (added whitespace before the TOC, added other whitespace in the task's preamble.) |
(Added Elixir) |
||
Line 264: | Line 264: | ||
[0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9] |
[0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9] |
||
using 10 writes.</pre> |
using 10 writes.</pre> |
||
=={{header|Elixir}}== |
|||
{{trans|Ruby}} |
|||
<lang elixir>defmodule Sort do |
|||
def cycleSort(list) do |
|||
tuple = List.to_tuple(list) |
|||
# Loop through the array to find cycles to rotate. |
|||
{data,writes} = Enum.reduce(0 .. tuple_size(tuple)-2, {tuple,0}, fn cycleStart,{data,writes} -> |
|||
item = elem(data, cycleStart) |
|||
pos = find_pos(data, cycleStart, item) |
|||
if pos == cycleStart do |
|||
# If the item is already there, this is not a cycle. |
|||
{data, writes} |
|||
else |
|||
# Otherwise, put the item there or right after any duplicates. |
|||
{data, item} = swap(data, pos, item) |
|||
rotate(data, cycleStart, item, writes+1) |
|||
end |
|||
end) |
|||
{Tuple.to_list(data), writes} |
|||
end |
|||
# Rotate the rest of the cycle. |
|||
defp rotate(data, cycleStart, item, writes) do |
|||
pos = find_pos(data, cycleStart, item) |
|||
{data, item} = swap(data, pos, item) |
|||
if pos==cycleStart, do: {data, writes+1}, |
|||
else: rotate(data, cycleStart, item, writes+1) |
|||
end |
|||
# Find where to put the item. |
|||
defp find_pos(data, cycleStart, item) do |
|||
cycleStart + Enum.count(cycleStart+1..tuple_size(data)-1, &elem(data, &1) < item) |
|||
end |
|||
# Put the item there or right after any duplicates. |
|||
defp swap(data, pos, item) when elem(data, pos)==item, do: swap(data, pos+1, item) |
|||
defp swap(data, pos, item) do |
|||
{put_elem(data, pos, item), elem(data, pos)} |
|||
end |
|||
end |
|||
IO.inspect a = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6] |
|||
{b, writes} = Sort.cycleSort(a) |
|||
IO.puts "writes : #{writes}" |
|||
IO.inspect b</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|Go}}== |
=={{header|Go}}== |
||
Line 736: | Line 789: | ||
There were 50 writes |
There were 50 writes |
||
After sorting: a a b b c c d d e e f f g g h h i i j j k k l l m m n n o o p p q q r r s s t t u u v v w w x x y y z z</pre> |
After sorting: a a b b c c d d e e f f g g h h i i j j k k l l m m n n o o p p q q r r s s t t u u v v w w x x y y z z</pre> |
||
=={{header|Perl 6}}== |
=={{header|Perl 6}}== |
||
<lang perl6>sub cycle_sort ( @nums ) { |
<lang perl6>sub cycle_sort ( @nums ) { |