Sorting algorithms/Cycle sort: Difference between revisions

</pre>

=={{header|FreeBASIC}}==

Uses algorithm in Wikipedia article:

<lang freebasic>' FB 1.05.0 Win64

' sort an array in place and return the number of writes

Function cycleSort(array() As Integer) As Integer

Dim length As Integer = UBound(array) - LBound(array) + 1

If Length = 0 Then Return 0

Dim As Integer item, position, writes = 0

' loop through the array to find cycles to rotate

For cycleStart As Integer = LBound(array) To UBound(array) - 1

item = array(cycleStart)

' find where to put the item

position = cycleStart

For i As Integer = cycleStart + 1 To UBound(array)

If array(i) < item Then position += 1

Next i

' If the item is already there, this is not a cycle

If position = cycleStart Then Continue For

' Otherwise, put the item there or right after any duplicates

While item = array(position)

position += 1

Wend

Swap array(position), item

writes += 1

'rotate the rest of the cycle

While position <> cycleStart

' Find where to put the item

position = cycleStart

For i As Integer = cycleStart + 1 To UBound(array)

If array(i) < item Then position += 1

Next i

' Put the item there or right after any duplicates

While item = array(position)

position += 1

Wend

Swap array(position), item

writes +=1

Wend

Next cycleStart

Return writes

End Function

Sub printArray(array() As Integer)

For i As Integer = LBound(array) To UBound(array)

Print Str(array(i)); " ";

Next

Print

End Sub

Dim array(1 To 16) As Integer = {0, 1, 2, 2, 2, 2, 1, 9, 3, 5, 5, 8, 4, 7, 0, 6}

printArray(array())

Dim writes As Integer = cycleSort(array())

Print "After sorting with"; writes; " writes :"

printArray(array())

Print

Dim array2(1 To 20) As Integer = {38, 119, 38, 33, 33, 28, 24, 101, 108, 120, 99, 59, 69, 24, 117, 22, 90, 94, 78, 75}

printArray(array2())

writes = cycleSort(array2())

Print "After sorting with"; writes; " writes :"

printArray(array2())

Print

Print "Press any key to quit"

Sleep</lang>

{{out}}

<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