Cycle Sort
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. It is based on the idea that the permutation to be sorted can be factored into cycles, which can individually be rotated to give a sorted result.
## # Python's algorithm of Cycle sort def cycle_sort(num_list): "Sort a list in place and return the number of writes." writes = 0 # Loop through the list to find cycles to rotate. for list_start, item in enumerate(num_list): # Find where to put the item. pos = list_start for item2 in num_list[list_start + 1:]: if item2 < item: pos += 1 # If the item is already there, this is not a loop. if pos == list_start: continue # Otherwise, put the item there or right after any duplicates. while item == num_list[pos]: pos += 1 num_list[pos], item = item, num_list[pos] writes += 1 # Rotate the rest of the loop. while pos != list_start: # Find where to put the item. pos = list_start for item2 in num_list[list_start + 1:]: if item2 < item: pos += 1 # Put the item there or right after any duplicates. while item == num_list[pos]: pos += 1 num_list[pos], item = item, num_list[pos] writes += 1 return writes num_list = [75, 16, 55, 19, 48, 14, 2, 61, 22, 100] print("Before: ", num_list) cycle_sort(num_list) print("After: ", num_list)
Sample output of above program.
C:\python\examples>pycodestyle --first cylesort.py
C:\python\examples>python cylesort.py
Before: [75, 16, 55, 19, 48, 14, 2, 61, 22, 100]
After: [2, 14, 16, 19, 22, 48, 55, 61, 75, 100]
C:\python\examples>
C:\python\examples>python cylesort.py
Before: [75, 16, 55, 19, 48, 14, 2, 61, 22, 100]
After: [2, 14, 16, 19, 22, 48, 55, 61, 75, 100]
C:\python\examples>
2018-07-20T16:29:57+05:30
2018-07-20T16:29:57+05:30
Amit Arora
Amit Arora
Python Programming Tutorial
Python
Practical Solution