# Python Data Structures and Algorithms: Sort a list of elements using Cycle sort

## Python Search and Sorting : Exercise-16 with Solution

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:**

```
# License: https://bit.ly/2V5W81t
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))
```

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.

**Flowchart: **

**Python Code Editor:**

** Contribute your code and comments through Disqus.**

**Previous:** Write a Python program to sort a list of elements using Comb sort.

**Next:** Write a Python program to sort a list of elements using Heap sort.

**What is the difficulty level of this exercise?**

Test your Python skills with w3resource's quiz

## Python: Tips of the Day

**Python: Convert byte to a string?**

You need to decode the bytes object to produce a string:

>>> b"abcde" b'abcde' # utf-8 is used here because it is a very common encoding, but you # need to use the encoding your data is actually in. >>> b"abcde".decode("utf-8") 'abcde'

Ref: https://bit.ly/2YuvClI

**New Content published on w3resource :**- Python Numpy exercises
- Python GeoPy Package exercises
- Python Pandas exercises
- Python nltk exercises
- Python BeautifulSoup exercises
- Form Template
- Composer - PHP Package Manager
- PHPUnit - PHP Testing
- Laravel - PHP Framework
- Angular - JavaScript Framework
- React - JavaScript Library
- Vue - JavaScript Framework
- Jest - JavaScript Testing Framework