Cycle Sort | Function sort the array using Cycle sort ; count number of memory writes ; traverse array elements and put it to on the right place ; initialize item as starting point ; Find position where we put the item . We basically count all smaller elements on right side of item . ; If item is already in correct position ; ignore all duplicate elements ; put the item to it 's right position ; Rotate rest of the cycle ; Find position where we put the element ; ignore all duplicate elements ; put the item to it 's right position ; Driver code
function cycleSort ( arr , n ) { let writes = 0 ; for ( let cycle_start = 0 ; cycle_start <= n - 2 ; cycle_start ++ ) { let item = arr [ cycle_start ] ; let pos = cycle_start ; for ( let i = cycle_start + 1 ; i < n ; i ++ ) if ( arr [ i ] < item ) pos ++ ; if ( pos == cycle_start ) continue ; while ( item == arr [ pos ] ) pos += 1 ; if ( pos != cycle_start ) { let temp = item ; item = arr [ pos ] ; arr [ pos ] = temp ; writes ++ ; } while ( pos != cycle_start ) { pos = cycle_start ; for ( let i = cycle_start + 1 ; i < n ; i ++ ) if ( arr [ i ] < item ) pos += 1 ; while ( item == arr [ pos ] ) pos += 1 ; if ( item != arr [ pos ] ) { let temp = item ; item = arr [ pos ] ; arr [ pos ] = temp ; writes ++ ; } } } } let arr = [ 1 , 8 , 3 , 9 , 10 , 10 , 2 , 4 ] ; let n = arr . length ; cycleSort ( arr , n ) ; document . write ( " " + " " ) ; for ( let i = 0 ; i < n ; i ++ ) document . write ( arr [ i ] + " " ) ;