# Cycle Sort In Pythonby Isai Damier, Android Engineer @ Google

```#=======================================================================
#  Author: Isai Damier
#  Title: Cyclesort
#  Project: geekviewpoint
#  Package: algorithms
#
#  Statement:
#  Given a disordered list of integers (or any other items),
#  rearrange the integers in natural order.
#
#  Sample Input: [8,5,3,1,9,6,0,7,4,2,5]
#  Sample Output: [0,1,2,3,4,5,5,6,7,8,9]
#
#  Time Complexity of Solution:
#  Average Case O(n^2); Worst Case O(n^2).
#
#  Approach:
#    Given a sequence of objects, such as an array of integers; if the
#    elements are not arranged in order that is because some of them
#    have switched places among themselves. For example, [4,1,2,3,5,0]
#    is not in order because 4,5,0 have traded places (1 bad group).
#    [4,2,3,7,5,0,1] is not in order because 4,5,0 have traded places
#    mathematics, each group, bad or good, is known as a cycle or an
#    orbit.
#
#  The basis for cyclesort is that if the elements of each bad group
#    sequence would be sorted.
#
#  cyclesort has great merit because it improves the life expectancy
#    of computer memories. During cyclesort, each element is moved once
#    at maximum. Recall that each time the data in a block of memory is
#=======================================================================
def cyclesort( aList ):
writes = 0

for cs in range( len( aList ) - 1 ):
# assume the element at aList[cs] is out of place
seeker = aList[cs]
pos = cs
# find the correct position (pos) of seeker
for i in range( cs + 1, len( aList ) ):
if aList[i] < seeker:
pos += 1

# if seeker is already in correct position, move on
if pos == cs:
continue

# move index pos after duplicates if any
while seeker == aList[pos]:
pos += 1

# Make a switch: seeker gets index pos, its rightful
# home; whatever element was at pos is now the seeker
# in search of a rightful home.

seeker = set_value( aList, seeker, pos )
# track the number of writes
writes += 1

#  complete the current cycle before moving to the next
#  cycle. At the end of the current cycle, pos will
#  equal cs; which should make sense since a cycle
#  always ends where it began.

while pos != cs:
# same as block of code above
pos = cs
for i in range( cs + 1, len( aList ) ):
if aList[i] < seeker:
pos += 1

while seeker == aList[pos]:
pos += 1

seeker = set_value( aList, seeker, pos )
writes += 1

return writes

def set_value( aList, data, ndx ):
try:
return aList[ndx]
finally:
aList[ndx] = data
```
```import unittest
from algorithms import sorting

class Test( unittest.TestCase ):

def testCyclesort( self ):
A = [8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5]
result = sorting.cyclesort( A )
for i in range( 1, len( A ) ):
if A[i - 1] > A[i]:
self.fail( "cyclesort method fails." )
```