All Quicksort does is call this function - Partition!

Quicksort is an algorithm that has a ton of variation to it - Today, we break down this algorithm into its constituent parts, Partitioning and recursion, and try to understand what it is about Quicksort that stays the same between implementations, and what changes.
Timestamps For Your Convenience
0:00 Introduction
0:26 Basics of Quicksort
1:39 Introduction to Partioning
2:20 Relationship between Partitioning and Quicksort
2:39 The Quicksort "Driver"
5:01 Partitioning Algorithm #1: The Intuitive One
6:40 Partitioning Algorithm #2: Lomuto's Scheme
8:55 Partitioning Algorithm #3: Hoare's Scheme
11:57 Time Complexity of Partitioning
13:00 Time Complexity of Quicksort & Pivot Choice
15:18 Conclusion
Here's the pseudocode used in the video:
Main Quicksort Driver
proc QuickSort(array, start_index, end_index)
if start_index ≥ end_index
return array
endIf
pivot_index ← pick random integer between start_index and end_index
new_pivot_index, array ← Partition(array, start_index, end_index, pivot_index)
array ← QuickSort(array, start_index, new_pivot_index - 1)
array ← QuickSort(array, new_pivot_index + 1, end_index)
return array
endProc
Intuitive Partitioning Algorithm
proc Partition_Intuitive(array, start_index, end_index, pivot_index)
smaller_array ← create empty array
larger_array ← create empty array
pivot ← array[pivot_index]
for i from start_index to end_index (inclusive)
if array[i] ≤ pivot
add array[i] to smaller_array
else
add array[i] to larger_array
endIf
endFor
new_pivot_index ← start_index + length of smaller_array
replace array[start_index to new_pivot_index-1] with smaller_array
replace array[new_pivot_index] with pivot
replace array[new_pivot_index+1 to end_index] with larger_array
return new_pivot_index, array
endProc
Lomuto's Partitioning Scheme
proc Partition_Lomuto(array, start_index, end_index, pivot_index):
swap array[end_index] with array[pivot_index]
pivot ← array[end_index]
i ← start_index - 1 (before first element)
for j from start_index to end_index-1:
if array[j] ≤ pivot:
i ← i + 1
swap array[i] and array[j]
endIf
endFor
i ← i + 1 (set pivot location)
swap arr[i] and arr[right]
new_pivot_index ← i
return new_pivot_index, array
Hoare's Partitioning Scheme (Modified)
proc Partition_Hoare_FixedPivot(array, start_index, end_index, pivot_index)
mid ← floor((start_index + end_index) / 2)
swap array[pivot_index] with array[start_index]
pivot ← arr[start_index]
i ← start_index - 1
j ← end_index + 1
while True:
do i ← i + 1
while array[i] ＜ pivot
do j ← j - 1
while array[j] ＞ pivot
if i ≥ j:
swap array[start_index] and array[j]
return j, array
swap arr[i] and arr[j]
endProc
-----
Want to contribute to the channel? Consider using the "Super Thanks" feature above, or visit my website at nerdfirst.net/donate to find alternative ways to donate. Thank you!
-----
Disclaimer: Please note that any information is provided on this channel in good faith, but I cannot guarantee 100% accuracy / correctness on all content. Contributors to this channel are not to be held responsible for any possible outcomes from your use of the information.

[@chrise3402]

Welcome back :) and congratulations on your recent marriage! I always enjoy your videos, and I was glad to hear your absence was just for work and nothing less pleasant.

[@NERDfirst]

Hello and thank you very much for your comment! Really glad to hear you like my work! Yes, I've just been busy is all, but ultimately this is where my roots are and I'd love to do more video work, circumstances permitting!

[@XxDruidegoxX]

I think you did not mention the case [1,1,1,1,1,1,1,1,1], this would be consistently O(n^2) unless you use Hoare, as it will still divide in even sized partitions when values are equal. I think this would have been worth mentioning.
I did not really learn anything from the video as I already knew those things, but the explanation was clear and enjoyable!

[@NERDfirst]

Hello and thank you very much for your comment! Good shout, I completely missed the case in which all (or even most) of the elements are equal. Good point as well about Hoare's algorithm working well under these circumstances, thank you for sharing!

[@Tawkitoutti]

Im watching an old video of yours on sampling and jumped to this video. I think youre wildly entertaining with your videos but your audio lost good treble. as someone that messes with music, it was nice in the old video and makes it easier on the ears. Might be a change in the mic. That is all. Good content tho.

[@NERDfirst]

Hello and thank you for your comment! Yeah, I used to use a condenser mic at distance, so the quality is better at the expense of a lot more effort at noise removal. Now I'm using a cheap wireless mic, so that might explain the difference in quality.