forked from WilliamQLiu/python-examples
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquick_sort.py
More file actions
45 lines (30 loc) · 1.06 KB
/
quick_sort.py
File metadata and controls
45 lines (30 loc) · 1.06 KB
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
""" Quick Sort """
def quickSort(mylist):
quickSortHelper(mylist, 0, len(mylist)-1)
def quickSortHelper(mylist, first, last):
if first < last:
splitpoint = partition(mylist, first, last)
quickSortHelper(mylist, first, splitpoint-1)
quickSortHelper(mylist, splitpoint+1, last)
def partition(mylist, first, last):
pivotvalue = mylist[first]
leftmark = first+1
rightmark = last
done = False
while not done:
while leftmark <= rightmark and mylist[leftmark] <= pivotvalue:
leftmark += 1
while mylist[rightmark] >= pivotvalue and rightmark >= leftmark:
rightmark -= 1
if rightmark < leftmark:
done = True
else:
# swap
mylist[leftmark], mylist[rightmark] = mylist[rightmark], mylist[leftmark]
# swap
mylist[leftmark], mylist[rightmark] = mylist[rightmark], mylist[leftmark]
if __name__ == '__main__':
mylist = [54,26,93,17,77,31,44,55,20]
print "Original: ", mylist
quickSort(mylist)
print "Quick Sorted: ", mylist