Coding Challenge

Let's try implementing a famously faster sorting algorithm: the Quicksort! And visualize the process with p5.js! Code: thecodingtrain...
🕹️ p5.js Web Editor Sketch: editor.p5js.or...
🎥 Previous video: • Coding Challenge #142:...
🎥 Next video: • Coding Challenge 144: ...
🎥 All videos: • Coding Challenges
References:
📄 Quicksort on Wikipedia: en.wikipedia.o...
Videos:
🎞️ 15 Sorting Algorithms in 6 Minutes: • 15 Sorting Algorithms ...
🎥 async/await: • 16.13: async/await Par...
🔴 Coding Train Live 173: • Coding Train Live 173:...
Related Coding Challenges:
🚂 #114 Bubble Sort Visualization: • Coding Challenge #114:...
Timestamps:
0:02 Introducing the Quicksort algorithm and the Big O Notation!
1:19 A walk-through of the Quicksort algorithm
6:05 Starting to code!
8:12 Figuring out the partition function!
12:44 Writing out the partition function
14:11 Testing and debugging the algorithm
16:57 Adding delays to visualize Quicksort
21:12 Coloring the pivot points!
25:59 Some more debugging and customizations!
26:59 Discussing partition schemes and things you could do!
Editing by Mathieu Blanchette
Animations by Jason Heglund
Music from Epidemic Sound
🚂 Website: thecodingtrain....
👾 Share Your Creation! thecodingtrain...
🚩 Suggest Topics: github.com/Cod...
💡 GitHub: github.com/Cod...
💬 Discord: thecodingtrain...
💖 Membership: kzbin.info...
🛒 Store: standard.tv/co...
🖋️ Twitter: / thecodingtrain
📸 Instagram: / the.coding.train
🎥 Coding Challenges: • Coding Challenges
🎥 Intro to Programming: • Start learning here!
🔗 p5.js: p5js.org
🔗 p5.js Web Editor: editor.p5js.org/
🔗 Processing: processing.org
📄 Code of Conduct: github.com/Cod...
This description was auto-generated. If you see a problem, please open an issue: github.com/Cod...
#sortingvisualization #quicksortalgorithm #p5js #javascript
🤖This video is sponsored by Brilliant: brilliant.org/... 🤖

[@hankhill-]

I've waited so long for this video! 👍 Actually I have to confess: Last August (once you made the video about your bubble sort visualization) I decided to use 'Visualization of Sorting Algorithms' as the topic for my upcoming term paper in computer science at school. And so I did it. All the time I was hoping that you are going to continue this series. But unfortunately you haven't. So I was forced to work on my own for the rest of the term paper. I've made research on five different sorting algorithms and visualized them in javascript using p5. Retrospectively this outcome was even better than expected. It helped me to understand the whole topic and taught me that cheating in something like this isn't helpful at all. Nevertheless thank you so much for your great, funny and awesome work all the time!!! 👍 P.S.: I'm 17 currently, doing my A-Levels, come from Germany and really got the best grade possible for this project (in GER it's 15 Points ;D ). My english isn't that good... I know but I hope you could understand it ;D Keep up with your great work!!!

[@TheCodingTrain]

Thanks for your nice feedback!

[@ryaneakins7269]

This is very nice, but have you seen sorting algorithms visualised as Hungarian dances?

[@jakobwakob1044]

Thank you for so much for mentioning that, my life would've always been incomplete without having seen those videos!!

[@betfairtradingtips4948]

I have now :-D

[@jiffpop5143]

My computer science teacher showed that to my whole class

[@MajorMandyKitten]

Can I just say that I always appreciate your videos? they're super inspiring!

[@Taterzz]

i swear this dude is the bob ross of coding. he manages to make something intricate and often irritating to deal with entertaining and insightful.

[@dcts7526]

Wow this is by far the best explenation for QuickSort!! You have such an incredible talent abstract things in a simple way. I loved that you didnt explain the partition algorithm at first, explaining the overall strategy first and then breaking down part by part...! I can see the beauty of quicksort now so clearly! Thanks so much for your work!

[@jcjeong]

Thank you so much for taking the time to do this! PS instead of swap function, easy way to swap array elements in ES6 is: [ arr[a], arr[b] ] = [ arr[b], arr[a] ];

[@yuli1970]

"Maybe my diagraming and explaining isn't the greatest..." Bro, your whiteboard explanation was so to the point that I learned how a quick sort algorithm works in 6 minutes

[@mattshu]

I was obsessed with those sorting visualization videos and tried tinkering with making it in Java but this makes it much easier thank you!!

[@bapolino733]

15:40 typical debugging.... was this the only mistake. Oh no nevermind

[@grainfrizz]

I'm not a JavaScript programmer but when you where doing await to both quickSort I was shouting that's now synchronous, lol! And then I was hoping there's Task.All() you could use. Then voilà, Promise.All(); :) I never thought JS would be so much similar to C#.

[@angelcaru]

The async functions proposal was inspired by C#

[@kevnar]

I have a theory that Daniel Shiffman is actually an ultra genius, thinking 9 levels deep and doing 5D chess in his head on the fly. The mistakes he makes are on purpose, planned out exactly, just to help us all learn the process of debugging. If you've seen the 4D coordinate rotation stuff he did in his tesseract video, you know he's no dummy. Thanks, Daniel. You're a beautiful person.

[@erjonfanaj3562]

Hoare has a shuffle method first - lo at [0] , i at [1] , hi at array.length - 1 - 1st element in the array will be the pivot and you just need to follow the rules 1.If lo < i ; i++ 2.else if hi > lo; hi- - 3.else swap lo i 4. If swap ... lo is pivot. And every time you use rules,you continue with the rule that was true in the preview step. Simple

[@Benthebean_01]

Before I saw your videos, I was so confused about coding, then I saw them and I became great at coding. Thank you

[@jared8411]

I have read this in a text book and watched 4 vids so far and this is the best one for me, I feel I can actually take a crack at coding it now.

[@mayankmani545]

Can you do Gravity Sort as well? I saw some visualisations and it was one of the fastest algorithms, but I don't understand how it works. Pretty please?

[@qvistyboy]

kzbin.info/www/bejne/g5_IeZWLjd5-fsk - not the fastest

[@0xDEAD_Inside]

Blasphemy! Everyone knows Bogo Sort is the fastest sort algorithm!

[@SimonTiger]

@Kapil Singaria no. Bogo sort is one of the slowest sorting algorithms.

[@0xDEAD_Inside]

@@SimonTiger Dude what! It is the only algorithm with lower bound complexity O(1). It can sort a list instantly. Get your algorithm game up!

[@mayankmani545]

@@SimonTiger r/woosh

[@Birbone21]

19:40 When your quick sort algorithm is so quick that you had to add sleep timeout to slow it down.

[@guiusepeoneda7190]

Nice video as always. Just want to help with a correction: O notation doesn't refer to average cost of an algorithm, but it's WORST case, it means that the bubblesort will never cost more than n² and it's average could be lower than that

[@TheCodingTrain]

Thank you for the import clarification!

[@IngoBartling]

I did the same with students. First they learned to init an array with the numbers 1-100. Than we used the inner part of the bubble-sort to mix up the array. Afterwards we sorted the whole array again. A little transfer exercise was to implement the shaker-sort algorithm.

[@koji2171]

Excellent video. This is the 2nd video about quick sort that I watched with laughter.

[@borschetsky]

Hey! Nice! This video should be at trends:-) Thanks to you I’ve finally understood the classic quickSort implementation with memory complexity 0(n).

[@NavyBlueMan]

What about an actual coin flip? Like a 3d visualisation of a coin that you give a random upwards and angular velocity and see if it lands heads or tails?

[@michaelwalker1013]

Austin code it !

[@TanjoGalbi]

You did not need async and await in there at all. If you draw during the partition function steps you get every step of the sorting displayed. You were just over complicating it by using async and await :)

[@ianbarton1990]

Bogosort next?

[@Qgleuo]

Wow, you are an amazing teacher!

[@LithiumDeuteride-6]

By the way, the correct conditional exchange function. mov eax, [ecx][esi*4-1*4] mov edx, [ecx][esi*4] .if (sdword ptr edx < eax) mov [ecx][esi*4-1*4], edx mov [ecx][esi*4], eax mov bl, true .endif On superscalar processors, 1-2 clock cycles work (but maybe 3-4 clock cycles if the processor is old), if the data is in the cache of the 1st level.

[@robertchen9979]

27:04 Another reason I think the visualization looks different is because multiple parts of the array are being partitioned at the same time (I guess that's what you wanted, but it's kinda like sorting in parallel). Also if you want to visualize the partition being done sequentially, I think you can draw everytime you swap, that way you can visualize quick sort (any many other sorting algorithms) without doing it asynchronously.

[@cin5mada]

Great Video. Really having a bad time with recursiveness and sorting algorithms. But this channel helps me a lot. Have a great day mister!

[@franzschubert4480]

1:02 Recursion is never required but an optional feature to many programming languages.

[@snoozemonster5669]

Have fun computing the ackermann numbers :

[@-Average-]

2nd year Computer Science student here.... I finally understand quicksort

[@rrschach2886]

Do the Thanos sort ! (Randomly delete half of the array until it is sorted)

[@zinsy23]

OMG! I've been having a problem where I want to add a delay to something but I want the draw loop to continue working. I think the async/await is my answer to the problem! I'm not getting answers I want on forums, but I think this is the answer! Now I just have to find time to come back to the project and test it!

[@jordy15322]

As always a great video :D and a great way of me procrastinating... at least this one was kind of revision. what about creating a series for the other sorting algorithms such as shell sort (it's a nice one to watch) and a few of the other ones too. Makes it a good tool for uni students etc to watch your content, in fact just the other day i gave the link to some people in my class to one of your other videos explaining something better than one of our lectuer's

[@axeleblaze6691]

Thanks a lot !! i was waiting for this , you are the best

[@JohnSmith-cj2zl]

Im only here to understand how to write a quicksort I wasnt disappointed, thank you for the diagram and your explanation.

[@byejason]

To be clear, use of await Promise.all() in this example did not result in both calls to quickSort() running in parallel on separate threads. Javascript is single threaded. The use of await and the sleep() function had the affect of running portions of each quickSort synchronously, jumping between the two as each executed a sleep().

[@Jkauppa]

try hash sort, with hash values to assign to bins, ie, 5 bins, min=5, max=106, delta=106-5, binsize=delta/bins=101/5=20.2, first bin is roughly [5, 5+20]=[5, 26], then [26, 46], [46, 66], [66, 86], [86,106]. hash function is simply f(value)=(value-min)/delta, giving the bin index of 1-bins. very much like radix and merge sort, and quick sort, division sort. subsort each bin, until all bins have max 1 number, then print in order.

[@Jkauppa]

try 2-phase median bucket sort, it first finds the actual median O(n), then split to two buckets, binary quicksort, then sort sub-buckets, O(n log n) stable always

[@trankie70144]

Best video I've evere seen 😂

[@justinbrentwood1299]

Coding Challenge: Merge Sort. :) I like this one.

[@karthikeshwar]

You are inspirational. Thanks a lot.

[@ferociousfeind8538]

How I'd do the pivot array- For every call to QuickSort, push our pivot index to the pivots array (after we've moved it into place) so that you can watch QuickSort sort one element at a time

[@Erik31415]

Your editor is a genious

[@johnmclennon7388]

As always well, can you make videos about sorts types(bubble sort, insertion sort, merge sort), it may be nice and useful.

[@Hagledesperado]

14:10 TypeScript would have caught 40% of those errors before you even ran the code. Juzzzt zzzaying.

[@noraxi]

That's a nice channel, glad i found it, keep up the good work

[@kae4881]

Whenever any programmer gets stuck with a project: 19:08

[@VictorNascimentoo]

Do a next challenge on Hilbert Curves and other space filling curves :)

[@TheCodingTrain]

Please suggest here! github.com/CodingTrain/Rainbow-Topics/issues

[@VictorNascimentoo]

@@TheCodingTrain There is this issue open since 2016 =( github.com/CodingTrain/Rainbow-Topics/issues/3

[@linsus]

Another cool thing would be Radix Sort LSD

[@efflogz5216]

Nice video as always, could you please do radix sort now?

[@dewinchy]

I need that thingy you blow in and it sounds like a locomotive, what is it called? :)

[@prakhiltp4636]

Nice explanation, thank you.

[@noname6878]

Mate Im pretty sure the partition function is the sum of the Boltzmann distribution over all the microstates of the system.

[@manuellehmann267]

Haha, a lot of mistakes this time. But don't be emberassed. Quick Sort can be pretty confusing. ^^

[@moradmorgan9268]

u are the best !!!!

[@funnyanimalworld7579]

It is really easy to do

[@TheFrankvHoof]

Could've/Should've colored the two elements currently swapping as well

[@TheCodingTrain]

So true. . .

[@Andrea-xo3ix]

The "Hoare Partition Scheme" is also known as "Your Mom's Partition Scheme" in most of the internet

[@sitalsitoula6536]

I am trying to do this by creating 10 circle and moving the circle each time a swap happens. When I test the animation without quicksort it works and the circle swap position. But when I put the code for quickSort and call the animate() function inside the swap() function all the circles move at the same time and don't get swapped as expected.

[@blinzi69]

please make a sudoku solver or anything that uses a recursive backtracking algorythm. would becool :) thanks

[@stickmandaninacan]

love sorting visualisations, but I think i might have a slight bit of ocd, since im triggered that all the sorted bars dont make a straight line. maybe instead of setting a bunch of bars with random height you could create the bars with incrementally ascending height so that they are straight when sorted, and then randomise their positions.

[@TheCodingTrain]

Oh I like this idea! Maybe if I do another sorting video I can do that.

[@siddhartha.c892]

In which application can we run the code

[@antoniong4380]

Sorry, but I just looked away 1 minute and I'm clueless even before looking away (Can't get to image out all the process)

[@thebigbang100]

You said "on average" when describing big O notation, but that's not really true, big O stands for the worst case complexity, or the upper bound.

[@TheCodingTrain]

Ah, yes, you are right! Ack, wish I could dub over my voice.

[@SummersonGoncalves]

greetings from Brazil!!!

[@basantabaruah990]

Please also do a video for merge sort.

[@teit-9_piyushbhujbal66]

Bro, why you always use javascript in each coding problem?

[@franatrturcech8484]

function quickSort(array){ if(array.length < 2) return array.slice(0); var arr = array.slice(0); var pivot = Math.floor(arr.length / 2); arr.splice(pivot, 1); var loet = [], gt = []; for(var num of arr) (num

[@grainfrizz]

I'm not sure but I think choosing the last element of the array as the first pivot point worsens the O performance especially in sorting items with billions of elements to sort. Is it right to start at ((arr.Length - 1) / 2) a.k.a the middle?

[@harikapachipulusu9243]

I think then it will become randomized quick sort, which is better in case of worst case.

[@juinjer]

something else entirely but an idea for a coding challenge is a trie data structure visualisation

[@utilisateurjulien363]

Hey would it be possible to implement something like this in Processing (not p5) ?

[@JDoawp]

That LSD sort next please

[@Cornellie]

Please do a Processing version for this. I dont know that async keyword :(

[@yuliantoyulianto6690]

sir please make tutorial about morphology technique in image processing uwing p5js. i have try to make it but got problem to make image kernell and scanning image.

[@joshkeegan3009]

Hey @The Coding Train , I am trying to access local files for a javascript project that I am working on in sublime. When I run the code, I get a cross origin error. This means that google Chrome is not trusting the file event though it is local. From the research I have done it seams like I need to run my javascript in a locally hosted web server. I can't find a good way of doing this on A MAC but think I have seen you doing it before. I would really appreciate the help.

[@TheCodingTrain]

This workflow video series will help! kzbin.info/aero/PLRqwX-V7Uu6Zu_uqEA6NqhLzKLACwU74X

[@ferociousfeind8538]

Recursive!??? I suppose the easiest way to implement it would be to call itself on the lefthand and righthand unsorted piles, instead of iteratively remembering which piles are which and remembering their bounds and keeping everything within one function without making calls to itself

[@krccmsitp2884]

You can do so, which would then be mergesort, not quicksort.

[@TheArcNgeL]

11:42 sorry but how is I not less than 5, arr[I] is not less than 5 yeah for it's 6, but I is less than 5, not very clear if you mix index and the value of the array at this index. :s [EDIT] ok I commented a bit early : It seems chat had the same issue as I did ^_^ .

[@adityachebiyyam2188]

On a sillier note, 14:13 - 16:51 strong arguments for switching to TypeScript 😅

[@vincenthubschmann6512]

15:48 how does his head make that noise ??

[@arcturianbeing2534]

love coding train 🚂 Can you do coupled pendulum. I’ve been struggling with this for a while now.

[@TheCodingTrain]

This? thecodingtrain.com/CodingChallenges/093-double-pendulum.html

[@muhammedshameel5684]

What about we sort with Neural Networks?

[@frognik79]

Now go back and update your image pixel sorter.

[@shabir301]

Word best short is count short O(2n) u can use if data in know range and finite number like a random number between 00000 -20000 ,

[@DungNguyen-kf5nk]

Sir, can you make some videos about design patterns :)

[@lionkor98]

I recommend "Design Patterns - Elements of Reusable Object-Oriented Software", the book, it's awesome. A must-have, in my opinion. ISBN 0-201-63361-2

[@iradnuriel9087]

yay!

[@REDACT3D]

number_list = [9, 3, 4, 6, 5] number_list.sort() print(number_list)

[@blockshift758]

There's no noise!!

[@divicii2001]

Merge sort. ? Daniel please

[@ZeroSleap]

16:09 all of these return errors and you not passing an array to swap, all of those just seem....javascript problems... The fact there was no redflags while editing is weird.

[@kosticnemanja1914]

what about [ new Set() ]

[@freezinfire]

Press and hold number key 5 on keyboard while the video is playing...

[@laurenzz3267]

Please do BOGO sort visualisation

[@wilsonwang8641]

Are you want to make me laughing to die? 😂

[@manikantajonnadula4327]

Can you make a 2 cars game

[@VY_Canis_Majoris]

Zinnia is my waifu

[@neuralwarp]

Now js has been improved, you should do some flood fill algorithms

[@isaacevans1176]

He always seems so frazzled

[@MartinLopez-rl2dk]

Anyone know what IDE he is using?

[@TheLshallo]

VS Code

[@yourteacher4353]

Like... like... LIKE!

[@mickyr171]

4th :p been waiting for another sorting vid lol

[@Xnoob545]

What is log? im 9 yrs old

[@APaleDot]

The graph of log(x) looks like this: www.desmos.com/calculator/sk49eevw7t You can see that as you go left on the graph, it becomes very flat. It doesn't rise very much. When talking about efficiency this means that as the size of the data increases (that is x) the amount of time it takes to process the data doesn't rise very much (that is log(x)).

[@sophiegrey9576]

quickstort