-
Notifications
You must be signed in to change notification settings - Fork 4
/
QuickSort.py
49 lines (33 loc) · 1.25 KB
/
QuickSort.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
#Name: MergeSort
#Author: Mateen SA
#Comments:
#Complexity: A quick sort is O(n * logn), but may degrade to O(n * n) ,
# if the split points are not near the middle of the list. It does not require additional space.
def quickSort(alist):
pivotValue = alist[0];
quickSortHelper(alist, pivotValue, 1, len(alist)-1);
def quickSortHelper(alist, pivotValue, first, last):
if first < last:
splitPosition = getPosition(alist, pivotValue, first, last);
quickSortHelper(alist, pivotValue, first, splitPosition - 1);
quickSortHelper(alist, pivotValue, splitPosition + 1, last);
def getPosition(alist, pivotValue, first, last):
done = False;
while not done:
while first <= last and alist[first] <= pivotValue:
first = first + 1;
while last >= first and alist[last] >= pivotValue:
last = last - 1;
if not first < last:
done = True;
else:
temp = alist[first];
alist[first] = alist[last];
alist[last] = temp;
temp = alist[first]
alist[first] = alist[last]
alist[last] = temp
return last;
alist = [54,26,93,17,77,31,44,55,20]
quickSort(alist)
print(alist)