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 https://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.