Sorting algorithms/Cycle sort: Difference between revisions
Add BCPL
Not a robot (talk | contribs) (Add BCPL) |
|||
Line 191:
-31 0 1 2 2 4 45 58 65 69 74 82 82 83 88 89 99 104 112 782
</pre>
=={{header|BCPL}}==
<lang bcpl>get "libhdr"
// Sort an array in place and return the number of writes
let cyclesort(v, len) = valof
$( let writes, temp = 0, ?
// Loop through the array to find cycles to rotate
for start = 0 to len-1
$( let item = v!start
// Find where to put the item
let pos = start
for i = start+1 to len-1
if v!i < item then pos := pos + 1
// If the item is already there, this is not a cycle
if pos = start loop
// Otherwise, put the item there or right after any duplicates
while item = v!pos do pos := pos + 1
temp := v!pos
v!pos := item
item := temp
writes := writes + 1
// Rotate the rest of the cycle
until pos = start
$( // Find where to put the item
pos := start
for i = start+1 to len-1
if v!i < item then pos := pos + 1
// Put the item there or right after any duplicates
while item = v!pos do pos := pos + 1
temp := v!pos
v!pos := item
item := temp
writes := writes + 1
$)
$)
resultis writes
$)
let writevec(v, len) be
$( for i = 0 to len-1 do
writef("%N ", v!i)
wrch('*N')
$)
let start() be
$( let v = table 0,1,2,2,2,2,1,9,3,5,5,8,4,7,0,6
let l = 16
let w = ?
writes("Before: ") ; writevec(v, l)
w := cyclesort(v)
writes("After: ") ; writevec(v, l)
writef("Writes: %N*N", w)
$)</lang>
{{out}}
<pre>Before: 0 1 2 2 2 2 1 9 3 5 5 8 4 7 0 6
After: 0 0 1 1 2 2 2 2 3 4 5 5 6 7 8 9
Writes: 10</pre>
=={{header|C}}==
| |||