Cycle Sort

Aakanksha Priya
ef cycleSort(arr):
  writes = 0
  # Loop through the arr to find cycles to rotate.
  for i in range(0, len(arr) - 1):
    item = arr[i]
    # Find where to put the item.
    pos = i
    for i in range(i + 1, len(arr)):
      if arr[i] < item:
        pos += 1
    # If the item is already there, this is not a cycle.
    if pos == i:
      continue
    # Otherwise, put the item there or right after any duplicates.
    while item == arr[pos]:
      pos += 1
    arr[pos], item = item, arr[pos]
    writes += 1
    # Rotate the rest of the cycle.
    while pos != i:
      # Find where to put the item.
      pos = i
      for i in range(i + 1, len(arr)):
        if arr[i] < item:
          pos += 1
      # Put the item there or right after any duplicates.
      while item == arr[pos]:
        pos += 1
      arr[pos], item = item, arr[pos]
      writes += 1
  return writes
#  driver code 
arr = [1, 8, 3, 9, 10, 10, 2, 4 ]
n = len(arr) 
cycleSort(arr)
print("After sort : ")
for i in range(0, n) : 
    print(arr[i], end = " ")