#
Cycle Sort In Python

#======================================================================= # 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 # and 2,3,7,1 have traded places (two bad groups). In discrete # 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 # were to return to their correct positions, then the entire # 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 # changed, the memory degrades. #======================================================================= 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." )