-
Notifications
You must be signed in to change notification settings - Fork 0
/
sorting_algo.py
115 lines (95 loc) · 2.74 KB
/
sorting_algo.py
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
def selection_sort(arr):
for i in range(len(arr)):
minV = arr[i]
index = i
for j in range(i+1,len(arr)):
if (arr[j]<minV):
minV = arr[j]
index = j
arr[i],arr[index] = arr[index], arr[i]
def insertion_sort(arr):
for i in range(1,len(arr)):
for j in range(i):
if arr[i-j] < arr[i-j-1]:
arr[i-j],arr[i-j-1] = arr[i-j-1],arr[i-j]
else:
break
return arr
def bubble_sort(arr):
flag = True
for i in range(1,len(arr)):
for j in range(len(arr)-i):
if arr[j] > arr[j+1]:
arr[j],arr[j+1] = arr[j+1],arr[j]
flag = False
if flag:
return
else:
flag = True
def quick_sort(arr):
left_sub_arr = []
right_sub_arr = []
if len(arr) <= 1:
return arr
pivot = arr[-1]
for i in range(len(arr)-1):
if arr[i]<pivot:
left_sub_arr.append(arr[i])
else:
right_sub_arr.append(arr[i])
return quick_sort(left_sub_arr)+[pivot]+quick_sort(right_sub_arr)
# def merge_sort(arr):
# if len(arr)<=1:
# return arr
# middle = len(arr)//2
# left_sub_arr = merge_sort(arr[:middle])
# right_sub_arr = merge_sort(arr[middle:])
# result = []
# while(True):
# if len(left_sub_arr) == 0:
# result += right_sub_arr
# break
# elif len(right_sub_arr) == 0:
# result += left_sub_arr
# break
# elif left_sub_arr[0] < right_sub_arr[0]:
# result.append(left_sub_arr.pop(0))
# else:
# result.append(right_sub_arr.pop(0))
# return result
#below code will still work but difference is that it modifies the
#given array but the above code returns new array without changing the
#given array.
def merge_sort(arr):
if len(arr)<=1:
return arr
middle = len(arr)//2
left_sub_arr = merge_sort(arr[:middle])
right_sub_arr = merge_sort(arr[middle:])
arr.clear()
while(True):
if len(left_sub_arr) == 0:
arr += right_sub_arr
break
elif len(right_sub_arr) == 0:
arr += left_sub_arr
break
elif left_sub_arr[0] < right_sub_arr[0]:
arr.append(left_sub_arr.pop(0))
else:
arr.append(right_sub_arr.pop(0))
return arr
array = [742,56,34,7,32,34,745,34,2,434,12,203]
arr2 = [742,56,34,7,32,34,745,34,2,434,12,203]
arr3 = [12,9]
# print(array)
# print(insertion_sort(array))
# bubble_sort(arr2)
# insertion_sort(arr3)
# insertion_sort(arr2)
# # insertion_sort(arr3)
# print(array)
merge_sort(arr2)
print(arr2)
# print(arr3)
# print(quick_sort(arr2))