1array = [29,99,27,41,66,28,44,78,87,19,31,76,58,88,83,97,12,21,44]
2
3quick_sort(array, 0, len(array) - 1)
4print(array)
5
1[12, 19, 21, 27, 28, 29, 31, 41, 44, 44, 58, 66, 76, 78, 83, 87, 88, 97, 99]
2
1def partition(array, start, end):
2 pivot = array[start]
3 low = start + 1
4 high = end
5
6 while True:
7 # If the current value we're looking at is larger than the pivot
8 # it's in the right place (right side of pivot) and we can move left,
9 # to the next element.
10 # We also need to make sure we haven't surpassed the low pointer, since that
11 # indicates we have already moved all the elements to their correct side of the pivot
12 while low <= high and array[high] >= pivot:
13 high = high - 1
14
15 # Opposite process of the one above
16 while low <= high and array[low] <= pivot:
17 low = low + 1
18
19 # We either found a value for both high and low that is out of order
20 # or low is higher than high, in which case we exit the loop
21 if low <= high:
22 array[low], array[high] = array[high], array[low]
23 # The loop continues
24 else:
25 # We exit out of the loop
26 break
27
28 array[start], array[high] = array[high], array[start]
29
30 return high
31
1def quick_sort(array, start, end):
2 if start >= end:
3 return
4
5 p = partition(array, start, end)
6 quick_sort(array, start, p-1)
7 quick_sort(array, p+1, end)
8