python-learning-codes/cycleSort.py at main · ChauhanDiya/python-learning-codes · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
# Python program to implement cycle sort

defcycleSort(array):
writes=0

# Loop through the array to find cycles to rotate.
forcycleStartinrange(0, len(array) -1):
item=array[cycleStart]

# Find where to put the item.
pos=cycleStart
foriinrange(cycleStart+1, len(array)):
ifarray[i] <item:
pos+=1

# If the item is already there, this is not a cycle.
ifpos==cycleStart:
continue

# Otherwise, put the item there or right after any duplicates.
whileitem==array[pos]:
pos+=1
array[pos], item=item, array[pos]
writes+=1

# Rotate the rest of the cycle.
whilepos!=cycleStart:

# Find where to put the item.
pos=cycleStart
foriinrange(cycleStart+1, len(array)):
ifarray[i] <item:
pos+=1

# Put the item there or right after any duplicates.
whileitem==array[pos]:
pos+=1
array[pos], item=item, array[pos]
writes+=1

returnwrites

# driver code
arr= [1, 8, 3, 9, 10, 10, 2, 4 ]
n=len(arr)
cycleSort(arr)

print("After sort : ")
foriinrange(0, n) :
print(arr[i], end=' ')