-
Notifications
You must be signed in to change notification settings - Fork 10
Expand file tree
/
Copy pathquicksort.py
More file actions
39 lines (33 loc) · 963 Bytes
/
quicksort.py
File metadata and controls
39 lines (33 loc) · 963 Bytes
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
import random
def quicksort(lyst):
quicksortHelper(lyst,0,len(lyst)-1)
def quicksortHelper(lyst,left,right):
if left<right:
pivotLocation = partition(lyst,left,right)
quicksortHelper(lyst,left,pivotLocation-1)
quicksortHelper(lyst,pivotLocation+1,right)
def partition(lyst,left,right):
middle = (left+right)//2
pivot = lyst[middle]
lyst[middle] = lyst[right]
lyst[right] = pivot
boundary = left
for index in range(left,right):
if lyst[index]<pivot:
swap(lyst,index,boundary)
boundary += 1
swap(lyst,right,boundary)
return boundary
def swap(lyst,a,b):
tmp = lyst[a]
lyst[a] = lyst[b]
lyst[b] = tmp
def main (size=20,sort=quicksort):
lyst = []
for count in range(size):
lyst.append(random.randint(1,size+1))
print(lyst)
quicksort(lyst)
print(lyst)
if __name__ == "__main__":
main()