-
Notifications
You must be signed in to change notification settings - Fork 4
/
quick_sort.py
81 lines (55 loc) · 1.99 KB
/
quick_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
from utils import file_reader as fr
class PivotType:
LAST = 'LAST'
FIRST = 'FIRST'
MEDIAN_OF_THREE = 'MEDIAN_OF_THREE'
@staticmethod
def values():
return [PivotType.LAST, PivotType.FIRST, PivotType.MEDIAN_OF_THREE]
def get_data():
return list(map(lambda s: int(s), fr.read_input(fr.FilePath.COMPARISONS)))
def quick_sort(pivot_type):
def find_pivot(array, i, j):
first, last = array[i], array[j - 1]
if pivot_type == PivotType.FIRST:
pivot = first
index = i
elif pivot_type == PivotType.LAST:
pivot = last
index = j - 1
elif pivot_type == PivotType.MEDIAN_OF_THREE:
size = j - i
mid_ind = ((i + j) // 2) - 1 if size % 2 == 0 else (i + j) // 2
mid = array[mid_ind]
mot = [[first, i], [mid, mid_ind], [last, j - 1]]
mot.sort()
pivot, index = mot[1]
return pivot, index
def partition(array, k, l):
pivot, index = find_pivot(array, k, l)
array[index] = array[k]
array[k] = pivot
i = k + 1
for j in range(k, l):
cur = array[j]
if cur < pivot:
array[j] = array[i]
array[i] = cur
i += 1
array[k] = array[i - 1]
array[i - 1] = pivot
return array, i - 1
def sort(array, comps, i, j):
if abs(j - i) <= 1:
return array, comps
array, index = partition(array, i, j)
array, comps_left = sort(array, index - i - 1, i, index)
array, comps_right = sort(array, j - index, index + 1, j)
return array, (comps + comps_left + comps_right)
data = get_data()
return sort(data, 0, 0, len(data))
def count_comparisons(pivot_type):
return quick_sort(pivot_type)
pivot_type = PivotType.MEDIAN_OF_THREE
numbers, comparisons = count_comparisons(pivot_type)
print('number of comparisons with pivot type %s = %d' % (pivot_type, comparisons))