-
Notifications
You must be signed in to change notification settings - Fork 0
/
sort.py
99 lines (85 loc) · 2.32 KB
/
sort.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
"""
Sorting algorithms
"""
def bubble_sort(array: list[int]) -> list[int]:
"""
Simplest sorting algorithm O(n^2)
:param array: Array to sort
:return: Sorted array
"""
array_size = len(array)
if array_size <= 1:
return array
for i in range(array_size):
swapped = False
for j in range(array_size - i - 1):
if array[j] > array[j + 1]:
array[j], array[j + 1] = array[j + 1], array[j]
swapped = True
if not swapped:
break
return array
def merge_sort(array: list[int]) -> list[int]:
"""
Divide and conquer, O(nlog(n))
:param array: Array to sort
:return: sorted array
"""
array_size = len(array)
if array_size <= 1:
return array
mid = array_size // 2
left = merge_sort(array[:mid])
right = merge_sort(array[mid:])
result = []
l_index = r_index = 0
while l_index < len(left) and r_index < len(right):
if left[l_index] <= right[r_index]:
result.append(left[l_index])
l_index += 1
else:
result.append(right[r_index])
r_index += 1
while l_index < len(left):
result.append(left[l_index])
l_index += 1
while r_index < len(right):
result.append(right[r_index])
r_index += 1
return result
def select_sort(array: list[int]) -> list[int]:
"""
Find required element in array and put it into desired place
:param array: Array to sort
:return: sorted array
"""
array_size = len(array)
for i in range(array_size):
min_idx = i
for j in range(i + 1, array_size):
if array[min_idx] > array[j]:
min_idx = j
array[i], array[min_idx] = array[min_idx], array[i]
return array
def quick_sort(array: list[int]) -> list[int]:
"""
Divide and conquer, O(nlog(n))
:param array: Array to sort
:return: sorted array
"""
array_size = len(array)
if array_size <= 1:
return array
mid = array_size // 2
pivot = array[mid]
left = []
right = []
equal = []
for i in array:
if i < pivot:
left.append(i)
elif i == pivot:
equal.append(i)
else:
right.append(i)
return quick_sort(left) + equal + quick_sort(right)