Uploaded January 2018 | Updated September 2026, 1 week ago
Previously, we looked at 2D Arrays that were large arrays containing smaller arrays. Inspired by a comment by YouTube user SimpletonGeek, today, we revisit the subject to look at a different technique of doing the same thing. This time, we simply use a flat array, but use math to work with it like it was two dimensional!
= CREDITS =
My appreciation extends to the creators of the following external assets that made this video possible:
Blown Away by Kevin MacLeod (incompetech.com)
Licensed under Creative Commons: By Attribution 3.0
creativecommons.org/licenses/by/3.0
ISRC: USUAN1200100
= 0612 TV =
0612 TV, a sub-project of NERDfirst.net, is an educational YouTube channel. Started in 2008, we have now covered a wide range of topics, from areas such as Programming, Algorithms and Computing Theories, Computer Graphics, Photography, and Specialized Guides for using software such as FFMPEG, Deshaker, GIMP and more!
Enjoy your stay, and don't hesitate to drop me a comment or a personal message to my inbox =) If you like my work, don't forget to subscribe!
Like what you see? Buy me a coffee → nerdfirst.net/donate
0612 TV Official Writeup: nerdfirst.net/0612tv
More about me: about.me/lcc0612
Official Twitter: twitter.com/0612tv
= NERDfirst =
NERDfirst is a project allowing me to go above and beyond YouTube videos into areas like app and game development. It will also contain the official 0612 TV blog and other resources.
Watch this space, and keep your eyes peeled on this channel for more updates! nerdfirst.net
-----
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.
Previously, we looked at 2D Arrays that were large arrays containing smaller arrays. Inspired by a comment by YouTube user SimpletonGeek, today, we revisit the subject to look at a different technique of doing the same thing. This time, we simply use a flat array, but use math to work with it like it was two dimensional!
= CREDITS =
My appreciation extends to the creators of the following external assets that made this video possible:
Blown Away by Kevin MacLeod (incompetech.com)
Licensed under Creative Commons: By Attribution 3.0
creativecommons.org/licenses/by/3.0
ISRC: USUAN1200100
= 0612 TV =
0612 TV, a sub-project of NERDfirst.net, is an educational YouTube channel. Started in 2008, we have now covered a wide range of topics, from areas such as Programming, Algorithms and Computing Theories, Computer Graphics, Photography, and Specialized Guides for using software such as FFMPEG, Deshaker, GIMP and more!
Enjoy your stay, and don't hesitate to drop me a comment or a personal message to my inbox =) If you like my work, don't forget to subscribe!
Like what you see? Buy me a coffee → nerdfirst.net/donate
0612 TV Official Writeup: nerdfirst.net/0612tv
More about me: about.me/lcc0612
Official Twitter: twitter.com/0612tv
= NERDfirst =
NERDfirst is a project allowing me to go above and beyond YouTube videos into areas like app and game development. It will also contain the official 0612 TV blog and other resources.
Watch this space, and keep your eyes peeled on this channel for more updates! nerdfirst.net
-----
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.


![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: Lomutos Scheme
8:55 Partitioning Algorithm #3: Hoares Scheme
11:57 Time Complexity of Partitioning
13:00 Time Complexity of Quicksort & Pivot Choice
15:18 Conclusion
Heres 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
*Lomutos 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
*Hoares 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. All Quicksort does is call this function - Partition!](https://i.ytimg.com/vi/iUXmmkftzzM/mqdefault.jpg)







