Cycle Sort in Python3
Below is an example of the Cycle Sort algorithm in Python3. See the Cycle Sort page for more information and implementations.
cycle-sort in Python3
def cycle_sort(array):
# loop from the beginning of the array to the second to last item
for currentIndex in range(0, len(array) - 1):
# save the value of the item at the currentIndex
item = array[currentIndex];
currentIndexCopy = currentIndex;
# loop through all indexes that proceed the currentIndex
for i in range(currentIndex + 1, len(array)):
if array[i] < item: currentIndexCopy += 1
i += 1
# if currentIndexCopy has not changed, the item at the currentIndex is already in the correct currentIndexCopy
if currentIndexCopy == currentIndex:
currentIndex += 1
continue
# skip duplicates
while item == array[currentIndexCopy]: currentIndexCopy += 1
# swap
temp = array[currentIndexCopy]
array[currentIndexCopy] = item
item = temp
# repeat above steps as long as we can find values to swap
while currentIndexCopy != currentIndex:
currentIndexCopy = currentIndex
# loop through all indexes that proceed the currentIndex
i = currentIndex + 1
while i < len(array):
if array[i] < item: currentIndexCopy += 1
i += 1
# skip duplicates
while item == array[currentIndexCopy]: currentIndexCopy += 1
# swap
temp = array[currentIndexCopy]
array[currentIndexCopy] = item
item = temp
currentIndex += 1
if __name__ == '__main__':
array = [12, 11, 15, 10, 9, 1, 2, 3, 13, 14, 4, 5, 6, 7, 8]
cycle_sort(array)
print(array)