cycle_sort.py

"""
Code contributed by Honey Sharma
Source: https://en.wikipedia.org/wiki/Cycle_sort
"""


defcycle_sort(array: list) ->list:
"""
 >>> cycle_sort([4, 3, 2, 1])
 [1, 2, 3, 4]

 >>> cycle_sort([-4, 20, 0, -50, 100, -1])
 [-50, -4, -1, 0, 20, 100]

 >>> cycle_sort([-.1, -.2, 1.3, -.8])
 [-0.8, -0.2, -0.1, 1.3]

 >>> cycle_sort([])
 []
 """
array_len=len(array)
forcycle_startinrange(array_len-1):
item=array[cycle_start]

pos=cycle_start
foriinrange(cycle_start+1, array_len):
ifarray[i] <item:
pos+=1

ifpos==cycle_start:
continue

whileitem==array[pos]:
pos+=1

array[pos], item=item, array[pos]
whilepos!=cycle_start:
pos=cycle_start
foriinrange(cycle_start+1, array_len):
ifarray[i] <item:
pos+=1

whileitem==array[pos]:
pos+=1

array[pos], item=item, array[pos]

returnarray


if__name__=="__main__":
assertcycle_sort([4, 5, 3, 2, 1]) == [1, 2, 3, 4, 5]
assertcycle_sort([0, 1, -10, 15, 2, -2]) == [-10, -2, 0, 1, 2, 15]