Sorting algorithms/Cycle sort: Difference between revisions
Add C |
Added Ruby |
||
Line 933: | Line 933: | ||
.swap: do p=p while x==@.p; end; parse value @.p x with x @.p;w=w+1;return</lang> |
.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. |
'''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}}== |
=={{header|Scala}}== |
Revision as of 07:54, 3 July 2014
For more information on cycle sorting, see the Wikipedia entry.
- See also
- Youtube Visualization and audibilization of Cycle Sort algorithm.
C
<lang C>
- include <stdio.h>
- include <stdlib.h>
int cycleSort(int * list, size_t l_len); void show_array(int * array, size_t a_len);
/*
* Sort an array in place and return the number of writes. */
int cycleSort(int * list, size_t l_len) {
int writes = 0;
/* Loop through the array to find cycles to rotate. */ for (int cycleStart = 0; cycleStart < l_len - 1; ++cycleStart) { int item = list[cycleStart]; int swap_tmp;
/* Find where to put the item. */ int pos = cycleStart; for (int i = cycleStart + 1; i < l_len; ++i) { if (list[i] < item) { ++pos; } }
/* If the item is already there, this is not a cycle. */ if (pos == cycleStart) { continue; }
/* Otherwise, put the item there or right after any duplicates. */ while (item == list[pos]) { ++pos; } swap_tmp = list[pos]; list[pos] = item; item = swap_tmp; ++writes;
/* Rotate the rest of the cycle. */ while (pos != cycleStart) { /* Find where to put the item. */ pos = cycleStart; for (int i = cycleStart + 1; i < l_len; ++i) { if (list[i] < item) { ++pos; } }
/* Put the item there or right after any duplicates. */ while (item == list[pos]) { ++pos; } swap_tmp = list[pos]; list[pos] = item; item = swap_tmp; ++writes; } }
return writes;
}
int main(int argc, char ** argv) {
int arr[] = { 0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6, }; int arr_k = sizeof(arr) / sizeof(arr[0]); int writes;
show_array(arr, arr_k); writes = cycleSort(arr, arr_k); show_array(arr, arr_k); printf("writes: %d\n", writes);
return 0;
}
void show_array(int * array, size_t a_len) {
for (int ix = 0; ix < a_len; ++ix) { printf("%d ", array[ix]); } putchar('\n'); return;
} </lang>
- Output:
0 1 2 2 2 2 1 9 3 5 5 8 4 7 0 6 0 0 1 1 2 2 2 2 3 4 5 5 6 7 8 9 writes: 10
D
This version doesn't use Phobos algorithms beside 'swap'. Algorithms can be used to find where to put the item1 and elsewhere.
<lang d>import std.stdio, std.algorithm;
/// Sort an array in place and return the number of writes. uint cycleSort(T)(T[] data) pure nothrow @safe @nogc {
typeof(return) nWrites = 0;
// Loop through the data to find cycles to rotate. foreach (immutable cycleStart, item1; data) { // Find where to put the item1. size_t pos = cycleStart; foreach (item2; data[cycleStart + 1 .. $]) if (item2 < item1) pos++;
// If the item1 is already there, this is not a cycle. if (pos == cycleStart) continue;
// Otherwise, put the item1 there or right after any duplicates. while (item1 == data[pos]) pos++; data[pos].swap(item1); nWrites++;
// Rotate the rest of the cycle. while (pos != cycleStart) { // Find where to put the item1. pos = cycleStart; foreach (item2; data[cycleStart + 1 .. $]) if (item2 < item1) pos++;
// Put the item1 there or right after any duplicates. while (item1 == data[pos]) pos++; data[pos].swap(item1); nWrites++; } }
return nWrites;
}
void main() {
immutable x = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]; auto xs = x.dup; immutable nWrites = xs.cycleSort;
if (!xs.isSorted) { "Wrong order!".writeln; } else { writeln(x, "\nIs correctly sorted using cycleSort to:"); writefln("%s\nusing %d writes.", xs, nWrites); }
}</lang>
- Output:
[0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6] Is correctly sorted using cycleSort to: [0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9] using 10 writes.
Go
This implementation was translated from the example code on Wikipedia.
<lang go>package main
import ( "fmt" "math/rand" "time" )
func cyclesort(ints []int) int { writes := 0
for cyclestart := 0; cyclestart < len(ints)-1; cyclestart++ { item := ints[cyclestart]
pos := cyclestart
for i := cyclestart + 1; i < len(ints); i++ { if ints[i] < item { pos++ } }
if pos == cyclestart { continue }
for item == ints[pos] { pos++ }
ints[pos], item = item, ints[pos]
writes++
for pos != cyclestart { pos = cyclestart for i := cyclestart + 1; i < len(ints); i++ { if ints[i] < item { pos++ } }
for item == ints[pos] { pos++ }
ints[pos], item = item, ints[pos] writes++ } }
return writes }
func main() { rand.Seed(time.Now().Unix())
ints := rand.Perm(10)
fmt.Println(ints) fmt.Printf("writes %d\n", cyclesort(ints)) fmt.Println(ints) }</lang>
- Output:
[1 9 3 5 8 4 7 0 6 2] writes 10 [0 1 2 3 4 5 6 7 8 9]
Note: output may be different due to the random numbers used.
J
J's sort is natively a single write sort, but it assigns the whole array at once. It would be trivial do the writes one at a time, and to avoid updating values which are not changed:
<lang J>noncyc=:3 :0
writes=. 0 for_item. /:~y do. if. item ~: item_index{y do. writes=. writes+1 y=.item item_index} y end. end. smoutput (":writes),' writes' y
)</lang>
Example use:
<lang J> noncyc 9 8 15 17 4 0 1 2 17 9 3 12 11 12 19 15 3 9 16 9 17 writes 0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</lang>
Meanwhile, if we just wanted the "value at a time swapping" mechanism, an idiomatic approach might look something like this:
<lang j>cyc0=:3 :0
c=. (#~ 1 < #@>)C./:/: y writes=. 0 for_box. c do. inds=. >box v=. ({:inds) { y for_ind. inds do. writes=. writes+1 t=. ind{ y y=. v ind} y v=. t end. end. smoutput (":writes),' writes' y
)</lang>
Example use:
<lang J> cyc0 9 8 15 17 4 0 1 2 17 9 3 12 11 12 19 15 3 9 16 9 18 writes 0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</lang>
This gives us an extra write, because we're using a generic cycle abstraction.
Also that's still a bit different from the wikipedia algorithm. We might model the wikipedia algorithm like this:
<lang J>cyc1=:3 :0
writes=. 0 for_index. i.(#y)-1 do. item=. index{y adj=. item+/ .>(1+index)}.y if. 0<adj do. pos=. index+adj while. item=pos{y do. pos=.pos+1 end. writes=. writes+1 t=. pos{y y=. item pos} y item=. t while. pos ~: index do. pos=. index+item+/ .>(1+index)}.y while. item=pos{y do. pos=.pos+1 end. writes=. writes+1 t=. pos{y y=. item pos} y item=. t end. end. end. smoutput (":writes),' writes' y
)</lang>
Example use:
<lang J> cyc1 9 8 15 17 4 0 1 2 17 9 3 12 11 12 19 15 3 9 16 9 17 writes 0 1 2 3 3 4 8 9 9 9 9 11 12 12 15 15 16 17 17 19</lang>
Note that we've saved a write in this case, by following the wikipedia algorithm.
Java
<lang java>import java.util.Arrays;
public class CycleSort {
public static void main(String[] args) { int[] arr = {5, 0, 1, 2, 2, 3, 5, 1, 1, 0, 5, 6, 9, 8, 0, 1};
System.out.println(Arrays.toString(arr));
int writes = cycleSort(arr); System.out.println(Arrays.toString(arr)); System.out.println("writes: " + writes); }
static int cycleSort(int[] a) { int writes = 0;
for (int cycleStart = 0; cycleStart < a.length - 1; cycleStart++) { int val = a[cycleStart];
// count the number of values that are smaller than val // since cycleStart int pos = cycleStart; for (int i = cycleStart + 1; i < a.length; i++) if (a[i] < val) pos++;
// there aren't any if (pos == cycleStart) continue;
// skip duplicates while (val == a[pos]) pos++;
// put val into final position int tmp = a[pos]; a[pos] = val; val = tmp; writes++;
// repeat as long as we can find values to swap // otherwise start new cycle while (pos != cycleStart) { pos = cycleStart; for (int i = cycleStart + 1; i < a.length; i++) if (a[i] < val) pos++;
while (val == a[pos]) pos++;
tmp = a[pos]; a[pos] = val; val = tmp; writes++; } } return writes; }
}</lang>
Output:
[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
NetRexx
Direct translation of the Wikipedia entry example <lang NetRexx>/* Rexx */ options replace format comments java crossref symbols nobinary
runSample(arg) return
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -- Sort an array in place and return the number of writes. method cycleSort(array = Rexx[]) public static
writes = 0
-- Loop through the array to find cycles to rotate. loop cycleStart = 0 to array.length - 1 - 1 item = array[cycleStart]
-- Find where to put the item. pos = cycleStart loop i = cycleStart + 1 to array.length - 1 if array[i] < item then pos = pos + 1 end i
-- If the item is already there, this is not a cycle. if pos == cycleStart then iterate
-- Otherwise, put the item there or right after any duplicates. loop while item == array[pos] pos = pos + 1 end swap_tmp = array[pos] array[pos] = item item = swap_tmp writes = writes + 1
-- Rotate the rest of the cycle. loop while pos \= cycleStart
-- Find where to put the item. pos = cycleStart loop i = cycleStart + 1 to array.length - 1 if array[i] < item then pos = pos + 1 end i
-- Put the item there or right after any duplicates. loop while item == array[pos] pos = pos + 1 end swap_tmp = array[pos] array[pos] = item item = swap_tmp writes = writes + 1
end
end cycleStart return writes
-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ method runSample(arg) public static
samples = ArrayList() samples.add([1, 9, 3, 5, 8, 4, 7, 0, 6, 2]) samples.add([0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6]) samples.add(['Greygill Hole', 'Ogof Draenen', 'Ogof Ffynnon Ddu', 'Malham Tarn Pot']) samples.add([-3.14 ,3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8, 4]) samples.add(['George Washington: Virginia', 'John Adams: Massachusetts', 'Thomas Jefferson: Virginia', 'James Madison: Virginia', 'James Monroe: Virginia'])
list = Rexx[] loop i_ = 0 to samples.size() - 1 list = Rexx[] samples.get(i_) say 'Input list ' Arrays.asList(list) writes = cycleSort(list) say 'Sorted list' Arrays.asList(list) say 'Total number of writes:' writes say end i_ return
</lang>
- Output:
Input list [1, 9, 3, 5, 8, 4, 7, 0, 6, 2] Sorted list [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] Total number of writes: 10 Input list [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6] Sorted list [0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9] Total number of writes: 10 Input list [Greygill Hole, Ogof Draenen, Ogof Ffynnon Ddu, Malham Tarn Pot] Sorted list [Greygill Hole, Malham Tarn Pot, Ogof Draenen, Ogof Ffynnon Ddu] Total number of writes: 3 Input list [-3.14, 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0, 2, 8, 8, 4] Sorted list [-3.14, 0, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 6, 6, 6, 7, 7, 8, 8, 8, 8, 8, 9, 9, 9, 9] Total number of writes: 34 Input list [George Washington: Virginia, John Adams: Massachusetts, Thomas Jefferson: Virginia, James Madison: Virginia, James Monroe: Virginia] Sorted list [George Washington: Virginia, James Madison: Virginia, James Monroe: Virginia, John Adams: Massachusetts, Thomas Jefferson: Virginia] Total number of writes: 4
ooRexx
<lang oorexx>/*REXX program demonstrates a cycle sort on a list of numbers**********
- 13.06.2014 Walter Pachl
- Modified from Rexx Version 2
- ooRexx allows to pass a stemmed variable by reference
- swapping variables uses a temporary instead of the parse.
- /
a.1='George Washington Virginia' a.2='John Adams Massachusetts' a.3='Thomas Jefferson Virginia' a.4='James Madison Virginia' a.5='James Monroe Virginia' n=5 Call show 'Unsorted list: ' w=sortcycle(a.,n) Say 'sorted' Call show 'Sorted list' Say ' ' Say 'This took' w 'writes.' Exit
sortcycle: Procedure
Use Arg a.,n writes=0 Do c=1 For n x=a.c p=c x=a.c Do j=c+1 To n If a.j<x Then p=p+1 End If p==c Then Iterate Do While x==a.p p=p+1 End t=x x=a.p a.p=t writes=writes+1 Do While p\==c p=c Do k=c+1 To n If a.k<x Then p=p+1 End Do While x==a.p p=p+1 End t=x x=a.p a.p=t writes=writes+1 End End Return writes
show:
Parse Arg hdr Say ' ' Say hdr Do i=1 To n Say format(i,2) a.i End Return</lang>
- Output:
Unsorted list: 1 George Washington Virginia 2 John Adams Massachusetts 3 Thomas Jefferson Virginia 4 James Madison Virginia 5 James Monroe Virginia sorted Sorted list 1 George Washington Virginia 2 James Madison Virginia 3 James Monroe Virginia 4 John Adams Massachusetts 5 Thomas Jefferson Virginia This took 4 writes.
Perl
This is based on the Wikipedia pseudocode. <lang perl>use strict; use warnings;
sub cycleSort(@) { my ($array) = @_; my $writes = 0;
my @alreadysorted;
# For each index except the last: for my $start ( 0 .. $#$array - 1 ) { next if $alreadysorted[$start]; my $item = $array->[$start]; # If there are N items less than $item, then we # must move $item N items rightward. my $pos = $start + grep $array->[$_] lt $item, $start + 1 .. $#$array; # If the item is where it should be, continue. next if $pos == $start; # If $item is one of several repetitions, move it to the right # of the last repeat. ++$pos while $item eq $array->[ $pos ]; # Store $item at $pos, where it belongs, and fetch the # value that had been at $pos, and put it in $item. ($array->[ $pos ], $item) = ($item, $array->[ $pos ]); ++$writes;
# Whatever $item is now, it certainly doesn't belong at $pos; do { # Find the correct $pos, $pos = $start + grep $array->[$_] lt $item, $start+1 .. $#$array; ++$pos while $item eq $array->[ $pos ]; # Swap the value there with $item, ($array->[ $pos ] , $item ) = ($item, $array->[ $pos ]); # And mark $pos as having the correct value in it.. $alreadysorted[ $pos ] = 1; ++$writes; # The loop ends after we have just written an item to $start } while $pos != $start; } $writes; }
use List::Util 'shuffle'; my @test = shuffle( ('a'..'z') x 2 ); print "Before sorting: @test\n"; print "There were ", cycleSort( \@test ), " writes\n"; print "After sorting: @test\n"; </lang>
- Output:
Before sorting: a t d b f g y l t p w c r r x i y j k i z q e v a f o q j u x k m h s u v z g m b o l e n h p n c s w d 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
Perl 6
<lang perl6>sub cycle_sort ( @nums is rw ) {
my $writes = 0;
# Loop through the array to find cycles to rotate. for @nums.kv -> $cycle_start, $item is copy {
# Find where to put the item. my $pos = $cycle_start + @nums[ $cycle_start ^.. * ].grep: * < $item;
# If the item is already there, this is not a cycle. next if $pos == $cycle_start;
# Otherwise, put the item there or right after any duplicates. $pos++ while $item == @nums[$pos]; ( @nums[$pos], $item ) .= reverse; $writes++;
# Rotate the rest of the cycle. while $pos != $cycle_start {
# Find where to put the item. $pos = $cycle_start + @nums[ $cycle_start ^.. * ].grep: * < $item;
# Put the item there or right after any duplicates. $pos++ while $item == @nums[$pos]; ( @nums[$pos], $item ) .= reverse; $writes++; } }
return $writes;
}
my @a = <0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6>;
say @a; say 'writes ', cycle_sort(@a); say @a; </lang>
- Output:
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
Python
The Wikipedia algorithm pseudocode is very nearly Python. The main changes needed were to change the name array to vector to stop it obscuring a built-in name, and iterating over an enumerated collection rather than using explicit indices.
<lang python>def cycleSort(vector):
"Sort a vector in place and return the number of writes." writes = 0 # Loop through the vector to find cycles to rotate. for cycleStart, item in enumerate(vector): # Find where to put the item. pos = cycleStart for item2 in vector[cycleStart + 1:]: if item2 < item: pos += 1 # If the item is already there, this is not a cycle. if pos == cycleStart: continue # Otherwise, put the item there or right after any duplicates. while item == vector[pos]: pos += 1 vector[pos], item = item, vector[pos] writes += 1 # Rotate the rest of the cycle. while pos != cycleStart: # Find where to put the item. pos = cycleStart for item2 in vector[cycleStart + 1:]: if item2 < item: pos += 1 # Put the item there or right after any duplicates. while item == vector[pos]: pos += 1 vector[pos], item = item, vector[pos] writes += 1 return writes
if __name__ == '__main__':
x = [0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6] xcopy = x[::] writes = cycleSort(xcopy) if xcopy != sorted(x): print('Wrong order!') else: print('%r\nIs correctly sorted using cycleSort to' '\n%r\nUsing %i writes.' % (x, xcopy, writes))</lang>
- Output:
[0, 1, 2, 2, 2, 2, 1, 9, 3.5, 5, 8, 4, 7, 0, 6] Is correctly sorted using cycleSort to [0, 0, 1, 1, 2, 2, 2, 2, 3.5, 4, 5, 6, 7, 8, 9] Using 10 writes.
REXX
version 1
<lang rexx>/* REXX ***************************************************************
- 12.06.2014 Walter Pachl translated from Wikipedia's code
- 20.06.2014 WP corrected (courtesy Alan Sampson)
- /
list='1 9 3 5 8 4 7 0 6 2' n=words(list) Do i=0 To n-1
array.i=word(list,i+1) End
Say list writes=cyclesort() Say 'writes='writes ol= Do i=0 To n-1
ol=ol array.i End
Say strip(ol) Exit
cycleSort: procedure expose array. n
writes = 0 -- Loop through the array to find cycles to rotate. do cycleStart=0 to n-2 item = array.cycleStart
-- Find where to put the item. pos = cycleStart Do i=cycleStart+1 to n-1 if array.i < item Then pos += 1 End
-- If the item is already there, this is not a cycle. if pos == cycleStart Then Iterate
-- Otherwise, put the item there or right after any duplicates. Do while item == array.pos pos += 1 End Parse Value array.pos item With item array.pos writes += 1
-- Rotate the rest of the cycle. Do while pos <> cycleStart
-- Find where to put the item. pos = cycleStart Do i=cycleStart + 1 to n-1 if array.i < item Then pos += 1 End
-- Put the item there or right after any duplicates. Do while item == array.pos pos += 1 End Parse Value array.pos item With item array.pos writes += 1 End End return writes</lang>
- Output:
1 9 3 5 8 4 7 0 6 2 writes=10 0 1 2 3 4 5 6 7 8 9
version 2
This REXX version demonstrates the use of negative numbers and non-integer values in the list.
As a default, the program uses (for the input list) some digits of pi, which for practical purposes, appear random. <lang rexx>/*REXX program demonstrates a cycle sort on a list of items. */ parse arg z /* [↓] not specified? Use π digs*/ if z= then z=-3.14 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 say 'unsorted list: ' z /*show the original unsorted #s. */ w=sortCycle(z) /*W: the # of writes done in sort*/ say 'and took' w 'writes.' /*show # of writes done in sort. */ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────SORTCYCLE subroutine────────────────*/ sortCycle: procedure expose @.; parse arg y; #=words(y); writes=0
do i=1 for #; @.i=word(y,i); end /*i*/ /*put items ───► @.*/ /* [↓] find cycles to rotate. */ do c=1 for #; x=@.c; p=c /*X is the item being sorted. */ do j=c+1 to #; if @.j<x then p=p+1; end /*where to put X.*/ if p==c then iterate /*Is it there? This ain't a cycle*/ do while x==@.p; p=p+1; end /*put X right after any duplicate*/ parse value @.p x with x @.p /*swap the two values: @.p and X.*/ writes=writes+1 /*bump counter for # of writes.*/ do while p\==c; p=c /*rotate the rest of the cycle. */ do k=c+1 to #; if @.k<x then p=p+1; end /*k*/ do while x==@.p; p=p+1; end /*put X here or right after dups.*/ parse value @.p x with x @.p /*swap the two values: @.p and X.*/ writes=writes+1 /*bump counter for # of writes.*/ end /*while p\==c*/ end /*c*/ /* [↓] display the sorted list. */
_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _ return writes</lang> output using the default input:
unsorted list: -3.14 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 sorted list: -3.14 0 1 1 2 2 2 2 2 3 3 3 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 7 7 8 8 8 8 8 9 9 9 9 and took 34 writes.
output using the input of: FM Stereo has been around since 1961.
unsorted list: FM Stereo has been around since 1961. sorted list: 1961. FM Stereo around been has since and took 7 writes.
Note (for the above output). This REXX program was executed on an ASCII machine.
On an ASCII machine, the order of sorting is numbers, uppercase letters, lowercase letters.
On an EBCDIC machine, the order of sorting is lowercase letters, uppercase letters, numbers.
Other (special) characters are also in a different order.
version 3
This version uses a faster (but a more cryptic) version of incrementing 1 (one) to P within two do loops. <lang rexx>/*REXX program demonstrates a cycle sort on a list of items. */ parse arg z /* [↓] not specified? Use π digs*/ if z= then z=-3.14 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 say 'unsorted list: ' z /*show the original unsorted #s. */ w=sortCycle(z) /*W: the # of writes done in sort*/ say 'and took' w 'writes.' /*show # of writes done in sort. */ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────SORTCYCLE subroutine────────────────*/ sortCycle: procedure expose @.; parse arg y; #=words(y); writes=0
do i=1 for #; @.i=word(y,i); end /*i*/ /*put items ───► @.*/ /* [↓] find cycles to rotate. */ do c=1 for #; x=@.c; p=c /*X is the item being sorted. */ do j=c+1 to #; if @.j<x then p=p+1; end /*where to put X.*/ if p==c then iterate /*Is it there? This ain't a cycle*/ do p=p while x==@.p; end /*put X right after any duplicate*/ parse value @.p x with x @.p /*swap the two values: @.p and X.*/ writes=writes+1 /*bump counter for # of writes. */ do while p\==c; p=c /*rotate the rest of the cycle. */ do k=c+1 to #; if @.k<x then p=p+1; end /*k*/ do p=p while x==@.p; end /*put X here or right after dups.*/ parse value @.p x with x @.p /*swap the two values: @.p and X.*/ writes=writes+1 /*bump counter for # of writes.*/ end /*while p\==c*/ end /*c*/ /* [↓] display the sorted list. */
_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _ return writes</lang> output is identical to the 2nd version.
version 4
This version uses a subroutine to perform the task of handling an (sorted) item placement (possibly after duplicates). <lang rexx>/*REXX program demonstrates a cycle sort on a list of items. */ parse arg z /* [↓] not specified? Use π digs*/ if z= then z=-3.14 3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7 9 5 0 2 8 8 4 say 'unsorted list: ' z /*show the original unsorted #s. */ w=sortCycle(z) /*W: the # of writes done in sort*/ say 'and took' w 'writes.' /*show # of writes done in sort. */ exit /*stick a fork in it, we're done.*/ /*──────────────────────────────────SORTCYCLE subroutine────────────────*/ sortCycle: procedure expose @.; parse arg y; #=words(y); w=0
do i=1 for #; @.i=word(y,i); end /*i*/ /*put items───►@.*/
do c=1 for #; x=@.c; p=c /*X is the item being sorted. */ do j=c+1 to #; if @.j<x then p=p+1; end /*j*/ /*where to put X*/ if p==c then iterate /*Is it there? This ain't a cycle*/ call .swap /*put X here or right after dups.*/ do while p\==c; p=c /*rotate the rest of the cycle. */ do k=c+1 to #; if @.k<x then p=p+1; end /*k*/ call .swap /*put X here or right after dups.*/ end /*while p\==c*/ end /*c*/ /* [↓] display the sorted list. */
_=@.1; do j=2 to #; _=_ @.j; end; say ' sorted list: ' _ return w /* [↓] find where to put X into @*/ .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 2nd version.
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>
- Output:
[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]
Scala
Translation of Java version <lang scala>
def cycleSort(a: Array[Int]): (Array[Int], Int) = { var writes = 0
for (cycleStart <- 0 until a.length - 1) { var value = a(cycleStart)
// count the number of values that are smaller than value since cycleStart var pos = cycleStart for (i <- cycleStart + 1 until a.length) if (a(i) < value) pos += 1
// skip if there aren't any if (pos != cycleStart) { // skip duplicates while (a(pos) == value) pos += 1
// put val into final position val tmp = a(pos) a(pos) = value value = tmp writes += 1
// repeat as long as we can find values to swap // otherwise start new cycle while (pos != cycleStart) { pos = cycleStart for (i <- cycleStart + 1 until a.length) if (a(i) < value) pos += 1
while (a(pos) == value) pos += 1
val tmp = a(pos) a(pos) = value value = tmp writes += 1 } } } (a, writes) }
</lang>
Tcl
Direct translation of the pseudocode on the Wikipedia page <lang tcl>proc cycleSort {listVar} {
upvar 1 $listVar array set writes 0
# Loop through the array to find cycles to rotate. for {set cycleStart 0} {$cycleStart < [llength $array]} {incr cycleStart} {
set item [lindex $array $cycleStart]
# Find where to put the item. set pos $cycleStart for {set i [expr {$pos + 1}]} {$i < [llength $array]} {incr i} { incr pos [expr {[lindex $array $i] < $item}] }
# If the item is already there, this is not a cycle. if {$pos == $cycleStart} continue
# Otherwise, put the item there or right after any duplicates. while {$item == [lindex $array $pos]} { incr pos } set tmp [lindex $array $pos] lset array $pos $item set item $tmp incr writes
# Rotate the rest of the cycle. while {$pos != $cycleStart} { # Find where to put the item. set pos $cycleStart
for {set i [expr {$cycleStart + 1}]} {$i < [llength $array]} {incr i} { incr pos [expr {[lindex $array $i] < $item}] }
# Put the item there or right after any duplicates. while {$item == [lindex $array $pos]} { incr pos } set tmp [lindex $array $pos] lset array $pos $item set item $tmp incr writes }
} return $writes
}</lang> Demonstrating: <lang tcl>set example {0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6} puts "Data was: $example" set writes [cycleSort example] puts "Data is now: $example" if {$example eq [lsort -real $example]} {
puts "\twhich is correctly sorted"
} else {
puts "\twhich is the wrong order!"
} puts "Writes required: $writes"</lang>
- Output:
Data was: 0 1 2 2 2 2 1 9 3.5 5 8 4 7 0 6 Data is now: 0 0 1 1 2 2 2 2 3.5 4 5 6 7 8 9 which is correctly sorted Writes required: 10