# Idea
A highly efficient sorting algorithm that follows the [[divide-and-conquer strategy]]. It involves three components:
- pivot selection: select one element and call that the pivot
- a element is a pivot if it satisfies the three conditions after sorting
- it's in the correct position in the sorted array
- items to its left are smaller
- items to its right are larger
- partition or pivot helper function to partition the original array into subarrays
- [[recursion]]
The key to good performance is to select good pivots. Ideally, you want the pivots to split the array into two even parts.
Like [[merge sort]], it exploits that fact that arrays of 0 or 1 element are always sorted.
The algorithm happens in-place. It doesn't create new arrays.
![[Quick Sort - Computerphile.mp4]]
## Big-O
Best or average case: Time complexity is $O(n \ log(n))$, where $n$ is the the number of items being sorted.
Worst case: $O(n^2)$, when the pivot happens to be the smallest or largest element repeatedly. The worst case is when the items are already sorted.
Space complexity is $O(log(n))$.
## Code
```python
def swap(my_list, index1, index2):
temp = my_list[index1]
my_list[index1] = my_list[index2]
my_list[index2] = temp
def pivot(my_list, pivot_index, end_index):
swap_index = pivot_index
for i in range(pivot_index + 1, end_index + 1):
if my_list[i] < my_list[pivot_index]:
swap_index += 1
swap(my_list, swap_index, i)
swap(my_list, pivot_index, swap_index)
return swap_index
def quick_sort(my_list, left, right):
if left < right: # if left == right, it means the subarray only as 1 element
pivot_index = pivot(my_list, left, right)
quick_sort(my_list, left, pivot_index - 1) # -1 is to exclude pivot
quick_sort(my_list, pivot_index + 1, right) # +1 is to move to the next item
return my_list
my_list = [4, 6, 1, 7, 3, 2, 5]
# my_list = [5, 2, 1, 8, 4, 7, 6, 3]
quick_sort(my_list, 0, len(my_list) - 1)
```
# References
- [Quick Sort - Computerphile - YouTube](https://www.youtube.com/watch?v=XE4VP_8Y0BU)
- [Quicksort: Partitioning an array - YouTube](https://www.youtube.com/watch?v=MZaf_9IZCrc)
- [Coding Challenge #143: Quicksort Visualization - YouTube](https://www.youtube.com/watch?v=eqo2LxRADhU)
- [Log In and Start Learning | Udemy](https://www.udemy.com/course/data-structures-algorithms-python/learn/lecture/27678322#overview)
- [Log In and Start Learning | Udemy](https://www.udemy.com/course/data-structures-algorithms-python/learn/lecture/27678336#overview)
- [Log In and Start Learning | Udemy](https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/learn/lecture/8344144#overview)
- [Log In and Start Learning | Udemy](https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/learn/lecture/8344176#overview)
- [Log In and Start Learning | Udemy](https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/learn/lecture/11072080#overview)
- [Log In and Start Learning | Udemy](https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/learn/lecture/11072080#overview)
- [Log In and Start Learning | Udemy](https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/learn/lecture/11072084#overview)