Sorting algorithms/Cycle sort: Difference between revisions
Content added Content deleted
No edit summary |
|||
Line 1,513: | Line 1,513: | ||
.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|Ring}}== |
|||
<lang ring> |
|||
# Project : Sorting algorithms/Cycle sort |
|||
# Date : 2018/02/17 |
|||
# Author : Gal Zsolt (~ CalmoSoft ~) |
|||
# Email : <calmosoft@gmail.com> |
|||
array = [0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6] |
|||
seearray(array) |
|||
writes = cyclesort(array) |
|||
see "after sorting with " + writes + " writes :" + nl |
|||
seearray(array) |
|||
see nl |
|||
array2 = [38, 119, 38, 33, 33, 28, 24, 101, 108, 120, 99, 59, 69, 24, 117, 22, 90, 94, 78, 75] |
|||
seearray(array2) |
|||
writes = cyclesort(array2) |
|||
see "after sorting with " + writes + " writes :" + nl |
|||
seearray(array2) |
|||
func cyclesort(array) |
|||
length = len(array) |
|||
if length = 0 |
|||
return 0 |
|||
ok |
|||
writes = 0 |
|||
for cyclestart = 1 to len(array) - 1 |
|||
item = array[cyclestart] |
|||
position = cyclestart |
|||
for i = cyclestart + 1 to len(array) |
|||
if array[i] < item |
|||
position = position + 1 |
|||
ok |
|||
next |
|||
if position = cyclestart |
|||
loop |
|||
ok |
|||
while item = array[position] |
|||
position = position+ 1 |
|||
end |
|||
temp = item |
|||
item = array[position] |
|||
array[position] = temp |
|||
writes = writes + 1 |
|||
while position != cyclestart |
|||
position = cyclestart |
|||
for i = cyclestart + 1 to len(array) |
|||
if array[i] < item |
|||
position = position + 1 |
|||
ok |
|||
next |
|||
while item = array[position] |
|||
position = position + 1 |
|||
end |
|||
temp = item |
|||
item = array[position] |
|||
array[position] = temp |
|||
writes = writes + 1 |
|||
end |
|||
next |
|||
return writes |
|||
func seearray(array) |
|||
for i = 1 to len(array) |
|||
see string(array[i]) + " " |
|||
next |
|||
see nl |
|||
</lang> |
|||
Output: |
|||
<pre> |
|||
0 1 2 2 2 2 1 9 3 5 5 8 4 7 0 6 |
|||
after sorting with 10 writes : |
|||
0 0 1 1 2 2 2 2 3 4 5 5 6 7 8 9 |
|||
38 119 38 33 33 28 24 101 108 120 99 59 69 24 117 22 90 94 78 75 |
|||
after sorting with 19 writes : |
|||
22 24 24 28 33 33 38 38 59 69 75 78 90 94 99 101 108 117 119 120 |
|||
</pre> |
|||
=={{header|Ruby}}== |
=={{header|Ruby}}== |