-
Notifications
You must be signed in to change notification settings - Fork 0
/
quickSortAlg.py
76 lines (62 loc) · 1.54 KB
/
quickSortAlg.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
'''
Created on July 4, 2021
@author: izakaria
'''
def swap(A, s1 , s2 ):
tmp = A[s1]
A[s1] = A[s2]
A[s2] = tmp
return A
def pivMedian(A):
n = len(A)
if n%2 == 0:
medianPos = ((n//2)-1)
else:
medianPos = n//2
if (A[0] > A[n-1] and A[0] < A[medianPos]) or (A[0] > A[medianPos] and A[0] < A[n-1]):
return 0
elif (A[n-1] > A[0] and A[n-1] < A[medianPos]) or (A[n-1] > A[medianPos] and A[n-1] < A[0]):
return n-1
else:
return medianPos
def choosePivotPos(A, type):
n = len(A)
if type == 1:
# first pivot
pivPos = 0
elif type == 2:
# last pivot
pivPos = n-1
else:
pivPos = pivMedian(A)
return pivPos
def partition(A):
p = A[0]
r = len(A)
i = 1
for j in range(1,r):
if A[j] < p:
A = swap(A,i,j)
i +=1
A = swap(A,0,i-1)
return A,i-1
def quickSortAlg(A, pivotType):
n = len(A)
if n>1:
p = choosePivotPos(A, pivotType)
A = swap(A,0,p)
A,pivotPos = partition(A)
A[:pivotPos], l = quickSortAlg(A[:pivotPos], pivotType)
A[pivotPos+1:], r = quickSortAlg(A[pivotPos+1:], pivotType)
return A, l+r+n-1
else:
return A,0
if __name__ == '__main__':
#with open('QuickSort.txt') as f:
# a = [int(x) for x in f]
a = [1,2,3,4,5]
#res = a[::-1]
(outPut, splitCount) = quickSortAlg(a, 3)
# print("outPut= ", outPut)
print("Spiltin Inv= ", splitCount)
pass