1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
def partition(array, left, right):
last_item = array[right]
pivot = last_item[0]
storeindex = left
for i in range(left, right):
if array[i][0] <= pivot:
array[i], array[storeindex] = array[storeindex], array[i]
storeindex += 1
# Move pivot to its final place
array[storeindex], array[right] = last_item, array[storeindex]
return storeindex
def quicksort(array, left, right):
# sort array[left:right+1] (i.e. bounds included)
if right > left:
pivotnewindex = partition(array, left, right)
quicksort(array, left, pivotnewindex - 1)
quicksort(array, pivotnewindex + 1, right)
def sort(array):
quicksort(array, 0, len(array) - 1)
|
