-
Notifications
You must be signed in to change notification settings - Fork 367
Expand file tree
/
Copy pathcyclic_sort.py
More file actions
42 lines (36 loc) · 1.1 KB
/
cyclic_sort.py
File metadata and controls
42 lines (36 loc) · 1.1 KB
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
#Approach: in-place swapping takes place by the formation of cycles.
# Time Complexity: O(n2)
# defination of an array
def cyclic_sort(array,temp,place):
count=0
# increment count
for num in array:
if num < temp:
count+=1
# if the number is not sorted
if temp != array[count]:
x=array[place]
array[place] = array[count]
array[count]= x
#recursively call function until sorted
cyclic_sort(array,array[place],place)
else:
if place <=(n-2):
cyclic_sort(array,array[place+1],place+1)
# print if sorted
else:
print("Sorted array is : ")
for i in range(0, n) :
print(array[i], end = " ")
if __name__=="__main__":
# Enter the number of elements
print("Enter the number of elements in an array : ")
n = int(input())
array = []
# Append the elements in the array
print("Enter the elements in an array : ")
for i in range(n):
x = int(input())
array.append(x)
# function call
cyclic_sort(array,array[0],0)