- runtime of $O(n logn)$
- space complexity of $O(logn)$
- recursive algorithm that uses a *pivot*
- items to left of pivot are smaller
- to the right are larger
- note that for partition, you use pivot as comparison value, but the index you return is not necessarily the pivot, it'll simply be the index of the first value of the sequence of values swapped from left that are *greater* than the pivot
```
def quick_sort_algorithm(array):
quick_sort(array, 0, len(array)-1)
def quick_sort(array, start, end):
if start < end:
mid = (start + end)//2
pivot = array[mid]
index = partition(array, start, end, pivot)
quick_sort(array, start, index-1)
quick_sort(array, index, end)
def partition(array, left, right, pivot):
while left <= right:
while array[left] < pivot:
left += 1
while array[right] > pivot:
right -= 1
if left <= right:
array[left], array[right] = array[right], array[left]
left += 1
right -= 1
return left
```
![[CleanShot 2024-08-22 at
[email protected]]]
![[CleanShot 2024-08-22 at
[email protected]]]
https://www.geeksforgeeks.org/time-and-space-complexity-analysis-of-quick-sort/
https://www.youtube.com/watch?v=pM-6r5xsNEY