-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathsorting_algorithms.py
140 lines (106 loc) · 3.38 KB
/
sorting_algorithms.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
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
import sys
from max_heap import max_heap
def merge_sort(nums):
if (len(nums) == 1 or len(nums) == 0):
return nums
first_half = nums[0 : int(len(nums) / 2)]
second_half = nums[int(len(nums) / 2) : len(nums)]
sorted_first_half = merge_sort(first_half)
sorted_second_half = merge_sort(second_half)
sorted_first_and_second_halfs = []
first_half_index = 0
second_half_index = 0
while (first_half_index < len(sorted_first_half) or second_half_index < len(sorted_second_half)):
if (first_half_index == len(sorted_first_half)):
while (second_half_index < len(sorted_second_half)):
sorted_first_and_second_halfs.append(sorted_second_half[second_half_index])
second_half_index += 1
elif (second_half_index == len(sorted_second_half)):
while (first_half_index < len(sorted_first_half)):
sorted_first_and_second_halfs.append(sorted_first_half[first_half_index])
first_half_index += 1
else:
if (sorted_first_half[first_half_index] <= sorted_second_half[second_half_index]):
sorted_first_and_second_halfs.append(sorted_first_half[first_half_index])
first_half_index += 1
else:
sorted_first_and_second_halfs.append(sorted_second_half[second_half_index])
second_half_index += 1
return sorted_first_and_second_halfs
def quick_sort(nums):
quick_sort_helper(nums, 0, len(nums) - 1)
return nums
def quick_sort_helper(nums, left_index, right_index):
if (left_index >= right_index):
return
pivot = nums[right_index]
pivot_index = sort_by_pivot(nums, left_index, right_index, pivot)
quick_sort_helper(nums, left_index, pivot_index - 1)
quick_sort_helper(nums, pivot_index + 1, right_index)
#return final index of the pivot
def sort_by_pivot(nums, left_index, right_index, pivot):
swap_index = left_index
for i in range(left_index, right_index):
curr = nums[i]
if (curr < pivot):
nums[i] = nums[swap_index]
nums[swap_index] = curr
swap_index += 1
nums[right_index] = nums[swap_index]
nums[swap_index] = pivot
return swap_index
def heap_sort(nums):
max_heap(nums)
def bubble_sort(array):
isSorted = False
counter = 0
while not isSorted:
isSorted = True
sortedFirstIndex = len(array) - 1 - counter
for i in range(0, sortedFirstIndex):
if array[i] > array[i + 1]:
swap(array, i, i + 1)
isSorted = False
counter += 1
return array
def swap(array, index1, index2):
temp = array[index1]
array[index1] = array[index2]
array[index2] = temp
def insertion_sort(nums):
for i in range(len(nums)):
curr = nums[i]
backwards_index = i - 1
while (0 <= backwards_index and curr < nums[backwards_index]):
#swap
temp = nums[backwards_index + 1]
nums[backwards_index + 1] = nums[backwards_index]
nums[backwards_index] = temp
backwards_index -= 1
return nums
def selection_sort(nums):
for i in range(len(nums) - 1):
index_of_minimum = i
minimum = nums[i + 1]
for j in range(i + 1, len(nums)):
curr = nums[j]
if (curr < minimum):
minimum = curr
index_of_minimum = j
if (i < len(nums) - 2):
#swap
nums[index_of_minimum] = nums[i]
nums[i] = minimum
return nums
def test_sort():
test_cases = [
[],
[0],
[0,1,2],
[2,1,0],
[3,5,2,0,8,7,9],
[9,8,7,6,5]
]
for i in range(len(test_cases)):
max_heap(test_cases[i])
test_sort()