Cycle Sort | Function sort the array using Cycle sort ; count number of memory writes ; Loop through the array to find cycles to rotate . ; initialize item as starting point ; Find where to put the item . ; If the item is already there , this is not a cycle . ; Otherwise , put the item there or right after any duplicates . ; put the item to it 's right position ; Rotate the rest of the cycle . ; Find where to put the item . ; Put the item there or right after any duplicates . ; put the item to it 's right position ; driver code
def cycleSort ( array ) : NEW_LINE INDENT writes = 0 NEW_LINE for cycleStart in range ( 0 , len ( array ) - 1 ) : NEW_LINE INDENT item = array [ cycleStart ] NEW_LINE pos = cycleStart NEW_LINE for i in range ( cycleStart + 1 , len ( array ) ) : NEW_LINE if array [ i ] < item : NEW_LINE INDENT pos += 1 NEW_LINE DEDENT if pos == cycleStart : NEW_LINE continue NEW_LINE while item == array [ pos ] : NEW_LINE pos += 1 NEW_LINE array [ pos ] , item = item , array [ pos ] NEW_LINE writes += 1 NEW_LINE while pos != cycleStart : NEW_LINE pos = cycleStart NEW_LINE for i in range ( cycleStart + 1 , len ( array ) ) : NEW_LINE INDENT if array [ i ] < item : NEW_LINE pos += 1 NEW_LINE DEDENT while item == array [ pos ] : NEW_LINE INDENT pos += 1 NEW_LINE DEDENT array [ pos ] , item = item , array [ pos ] NEW_LINE writes += 1 NEW_LINE DEDENT return writes NEW_LINE DEDENT arr = [ 1 , 8 , 3 , 9 , 10 , 10 , 2 , 4 ] NEW_LINE n = len ( arr ) NEW_LINE cycleSort ( arr ) NEW_LINE print ( " After ▁ sort ▁ : ▁ " ) NEW_LINE for i in range ( 0 , n ) : NEW_LINE INDENT print ( arr [ i ] , end = ' ▁ ' ) NEW_LINE DEDENT