Cycle Sort In Python
by Isai Damier

#=======================================================================
#  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." )