cycle sort Algorithm
Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is theoretically optimal in terms of the total number of writes to the original array, unlike any other in-place sorting algorithm. This matches the minimal number of overwrites need for a completed in-place sort.
Minimizing the number of writes is useful when make writes to some huge data set is very expensive, such as with EEPROMs like flash memory where each write reduces the lifespan of the memory.
# Code contributed by Honey Sharma
def cycle_sort(array):
ans = 0
# Pass through the array to find cycles to rotate.
for cycleStart in range(0, len(array) - 1):
item = array[cycleStart]
# finding the position for putting the item.
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
# If the item is already present-not a cycle.
if pos == cycleStart:
continue
# Otherwise, put the item there or right after any duplicates.
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
ans += 1
# Rotate the rest of the cycle.
while pos != cycleStart:
# Find where to put the item.
pos = cycleStart
for i in range(cycleStart + 1, len(array)):
if array[i] < item:
pos += 1
# Put the item there or right after any duplicates.
while item == array[pos]:
pos += 1
array[pos], item = item, array[pos]
ans += 1
return ans
# Main Code starts here
if __name__ == "__main__":
user_input = input("Enter numbers separated by a comma:\n")
unsorted = [int(item) for item in user_input.split(",")]
n = len(unsorted)
cycle_sort(unsorted)
print("After sort : ")
for i in range(0, n):
print(unsorted[i], end=" ")
