-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathalgorithum.py
More file actions
179 lines (117 loc) · 4 KB
/
Copy pathalgorithum.py
File metadata and controls
179 lines (117 loc) · 4 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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
import random
#bubbbleSort
def bubblesort(array):
for i in range (0, l - 1):
for j in range (0, l-1-i):
if array [j] > array[j+ 1]:
array[j], array[j+1] = array[j+1], array [j]
return array
#selectionsort
def selectionsort(array):
for i in range (0, l):
minimum = i
for j in range (i+1, l):
if array[minimum] > array[j]:
array[minimum], array[j] = array[j], array[minimum]
return array
#insertionsort
def insertionsort(sample):
for i in range(1, len(sample)):
j =i
while (j!=0 and sample[j] < sample[j-1]):
sample[j-1], sample[j] = sample[j], sample[j-1]
j -=1
#quick sort
def quick_sort(array):
ARRAY_LENGTH = len(array)
if( ARRAY_LENGTH <= 1):
return array
else:
PIVOT = array[0]
GREATER = [ element for element in array[1:] if element > PIVOT ]
LESSER = [ element for element in array[1:] if element <= PIVOT ]
return quick_sort(LESSER) + [PIVOT] + quick_sort(GREATER)
#merge sort
def mergeSort(alist):
if len(alist)>1:
mid = len(alist)//2
lefthalf = alist[:mid]
righthalf = alist[mid:]
mergeSort(lefthalf)
mergeSort(righthalf)
i=0
j=0
k=0
while i < len(lefthalf) and j < len(righthalf):
if lefthalf[i] < righthalf[j]:
alist[k]=lefthalf[i]
i=i+1
else:
alist[k]=righthalf[j]
j=j+1
k=k+1
while i < len(lefthalf):
alist[k]=lefthalf[i]
i=i+1
k=k+1
while j < len(righthalf):
alist[k]=righthalf[j]
j=j+1
k=k+1
#heap sort
def heapify (array, i , l) :
largest = i
left = 2*i + 1
right = 2*i + 2
if left < l and array[left] > array [largest]:
largest = left
if right < l and array [right] > array [largest] :
largest = right
if largest != i :
array[largest], array[i] = array[i], array[largest]
heapify(array, largest, l)
def heapsort (array):
l = len(array)
for i in range (l, -1,-1) :
heapify (array, i , l )
for i in range (l - 1, 0, -1):
array [0], array [i] = array [i], array [0]
heapify (array, 0 , i )
return array
print ('Number Sorting Program :\n \n ')
n = int(input('How many number you want to Sort: \n'))
print ('So you want to sort ', n, ' numbers.\n')
q = int(input('You are going to enter number\n 1. Manually \n Or we sort \n2. Random numbers , \n Choose corresponding number.'))
if q == 1 :
array = []
print ("Enter any number and hit Enter, repeat this process untill you enter ", n , "numbers.")
for i in range(n):
numbers = int(input("\n Enter any number: \t"))
array.append(numbers)
print ('\n List we are going to sort ', array)
if q == 2 :
array = [random.randint(1, 1000000) for _ in range(n)]
print(array)
l = len(array)
print ('\n Which sort you want to run : \n \n1. Bubble sort, \n2. Selection Sort, \n3. Insertion Sort, \n4. Quick Sort, \n5. Merge sort, \n6. Heap Sort ')
var = int(input ('\n \n Enter number for corresponding sorting Algorithum :'))
if var ==1 :
bubblesort(array)
print ('Bubble Sort : ',array)
elif var ==2 :
selectionsort (array)
print ('Selection Sort : ' , array)
elif var == 3 :
insertionsort (array)
print ('Insertion Sort : ',array)
elif var == 4 :
print ('Quick sort :', quick_sort(array))
elif var == 5 :
mergeSort (array)
print ('merge sort :', array)
elif var == 6 :
heapsort (array)
print ('Heap sort :', array)
else :
print ('Enter number to run Sort')
#task completed