# Python Example – Write a Python program to sort a list of elements using Cycle sort.

Hits: 7 # (Python Example for Citizen Data Scientist & Business Analyst)

Write a Python program to sort a list of elements using Cycle sort.

Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.

Sample Solution:

Python Code:

``````
def cycleSort(vector):
"Sort a vector in place and return the number of writes."
writes = 0

for cycleStart, item in enumerate(vector):

pos = cycleStart
for item2 in vector[cycleStart + 1:]:
if item2 < item:
pos += 1

if pos == cycleStart:
continue

while item == vector[pos]:
pos += 1
vector[pos], item = item, vector[pos]
writes += 1

while pos != cycleStart:

pos = cycleStart
for item2 in vector[cycleStart + 1:]:
if item2 < item:
pos += 1

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('%rnIs correctly sorted using cycleSort to'
'n%rnUsing %i writes.' % (x, xcopy, writes))
``````

Sample 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.```

## Write a Python program to sort a list of elements using Cycle sort

#### Free Machine Learning & Data Science Coding Tutorials in Python & R for Beginners. Subscribe @ Western Australian Center for Applied Machine Learning & Data Science. ```