Coding Challenge
ฝัง
- เผยแพร่เมื่อ 26 ก.ย. 2024
- 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: th-cam.com/users/the...
🛒 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/... 🤖
was looking for the visualization of quick sort....glad you made this video :)
There is a website called "visual go" u can find visualization for all sortings.
@@harikapachipulusu9243 thanks for the info 😊
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!!!
Thanks for your nice feedback!
Can I just say that I always appreciate your videos? they're super inspiring!
This is very nice, but have you seen sorting algorithms visualised as Hungarian dances?
Thank you for so much for mentioning that, my life would've always been incomplete without having seen those videos!!
I have now :-D
My computer science teacher showed that to my whole class
This was incredible, thank you so much I feel like i've made more progress on understanding this in the last half hour than I have all afternoon.
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.
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!
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] ];
I was obsessed with those sorting visualization videos and tried tinkering with making it in Java but this makes it much easier thank you!!
"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
For a better pivot: pivot = start/2 + end/2. This works better when the array is (already) sorted.
Oh, thanks for the tip!
I actually had to implement this algorithm last week! It's comforting knowing that I'm not the only one who struggled with a bunch of errors doing this! Hahaha
Before I saw your videos, I was so confused about coding, then I saw them and I became great at coding. Thank you
Good job, I like the fact you made a plan on the white board and then implemented it. Of course it will not work the first time, things take time to debug and optimize.
15:40 typical debugging.... was this the only mistake. Oh no nevermind
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.
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
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#.
The async functions proposal was inspired by C#
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.
Excellent video. This is the 2nd video about quick sort that I watched with laughter.
Just to note. Big-Oh notation is for the worst case (you have probably already been told this).
Bubble sort and Quick sort are both O(n^2). (In the worst case, the pivot is always terrible).
You're completely right about the average case though!
Why not use it for the average runtime or expected runtime? I've seen that countless times in literature.
@@alexmeyer2394
You're correct. The author defines the usage. In practice, I've used the notation for best, average, and worst case analysis of algorithms. Recently, I've been spending too much time on the latter.
Thanks for the correction!
Thank you for this discussion!!
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?
th-cam.com/video/MneHbUXyKHg/w-d-xo.html - not the fastest
Blasphemy! Everyone knows Bogo Sort is the fastest sort algorithm!
@Kapil Singaria no. Bogo sort is one of the slowest sorting algorithms.
@@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!
@@SimonTiger r/woosh
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
Thank you for the import clarification!
A *quick* explanation of QuickSort:
1. Pick a random element. That's your pivot.
2. Move elements larger than the pivot to the right, and elements smaller than the pivot to the left.
3. Put your pivot back between the 2 subarrays you just created. BOOM your pivot is in its sorted place!
4. Go to the first subarray and repeat the first 3 steps. Continue when you're at the start of the array.
5. After going all the way down, go back up subarray by subarray (ignoring the already sorted stuff) until you're at the top.
6. Done.
Dude u literally just cleared my confusion...thanks
19:40 When your quick sort algorithm is so quick that you had to add sleep timeout to slow it down.
this array handling in a function is very interesting. i didn't know could be a third constructor space to hold an array and flip through with more place holders
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.
Thank you for the information you gave us and I'm a fan of you. You are an amazing teacher.
Wow, you are an amazing teacher!
Hey! Nice!
This video should be at trends:-)
Thanks to you I’ve finally understood the classic quickSort implementation with memory complexity 0(n).
2nd year Computer Science student here.... I finally understand quicksort
Great Video. Really having a bad time with recursiveness and sorting algorithms.
But this channel helps me a lot.
Have a great day mister!
I have read books , watched lot of other TH-cam channels, this video made the day for me. So simple and clear.Choosing 5 elements is the good idea which made things simple to understand. Thank you!
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?
Austin code it !
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 :)
I would love to see a heap sort visualization, the heap has different levels and can be visualized with different colors, one of the best sorts to watch.
Thanks a lot !! i was waiting for this , you are the best
I did my thesis inspired by these videos
Im only here to understand how to write a quicksort I wasnt disappointed, thank you for the diagram and your explanation.
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
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.
1:02 Recursion is never required but an optional feature to many programming languages.
Have fun computing the ackermann numbers :
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.
Have you ever thought about making a video on the topic of Case Based Reasoning? I think it could be pretty interesting, maybe have a game like Tetris or Snake and have a CBR algorithm learn from your behavior. Love your videos, keep it up :)
Do the Thanos sort ! (Randomly delete half of the array until it is sorted)
You are inspirational. Thanks a lot.
Nice video. I was watching your video with the double pendulum, and decided to make one as well. Then i though "tripple pendulum?" i am sad that you had not made one yet, so i went ahead and made the pendulum myself, but I now challenge you to make one yourself :) looking forward to see if you can :P
If you do end up trying to make one, you will probably need lagrangian equations :D
mine is up and running here oxnan.me/p3
Wow! You can submit a link to the coding train website if you like!
github.com/CodingTrain/website/wiki/Community-Contributions-Guide
Okay :) thanks :)
Great video Daniel! id love to see mergesort visualization, greetings from Argentina!!
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!
Your editor is a genious
Bogosort next?
That's a nice channel, glad i found it, keep up the good work
Best video I've evere seen 😂
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.
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
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().
this is almost a good the Hungarian folk dance that my coding teacher showed me for a visualisation of a quick sort
Coding Challenge: Merge Sort. :) I like this one.
"I don't need to pass a partition argument because I'm always going to use the end as the pivot."
That said, quicksort with a random pivot generally performs better. That said, like any plain quicksort, it still would have O(n^2) in the worst case.
Nice explanation, thank you.
Whenever any programmer gets stuck with a project: 19:08
14:10 TypeScript would have caught 40% of those errors before you even ran the code. Juzzzt zzzaying.
wow, that one was pretty crazy.. wut a convenient delay , i could have used sumthing like this "so" many times by now. as for sorting it's still catastrophic for me lol should have seen what i came up for as a selection yesterday. fun and interesting to watch, not sure it has a real use .learned to use my push pop shfft unshift slice concat and filter and queue up indexs to move and delete by splitting the array moving from middle to front. as far as the big o goes, i guess prettty big. and i nested a loop, and used my upper outside one to select a number, and the inside one checked each one at a time and find the biggest on so y[j] > y[i]?, moves on, checks them all, and finds the biggest,excluding ones it found.slices it from the middle, pops it off the end pushes it to end of second slice and concats it. it gets, some, kinda close, lol then i came here lollol
As always well, can you make videos about sorts types(bubble sort, insertion sort, merge sort), it may be nice and useful.
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
Another cool thing would be Radix Sort LSD
Do a next challenge on Hilbert Curves and other space filling curves :)
Please suggest here! github.com/CodingTrain/Rainbow-Topics/issues
@@TheCodingTrain There is this issue open since 2016 =( github.com/CodingTrain/Rainbow-Topics/issues/3
Nice video as always, could you please do radix sort now?
Haha, a lot of mistakes this time. But don't be emberassed. Quick Sort can be pretty confusing. ^^
Could've/Should've colored the two elements currently swapping as well
So true. . .
Wow. With the visualization part I really understand the concept more practically.
I came up with some control, if the end is greater than the array.length - 1 (last item's position), the sorting will fill in undefined values in the remaining places. So it's really good to check for it, gracefully.
let ending = end > array.length - 1? array.length - 1 : end
The "Hoare Partition Scheme" is also known as "Your Mom's Partition Scheme" in most of the internet
It is really easy to do
greetings from Brazil!!!
u are the best !!!!
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.
um what about the value at index? You're segmenting from start to index - 1, and index + 1 to end. So what about the value at index?
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.
Ah, yes, you are right! Ack, wish I could dub over my voice.
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.
Oh I like this idea! Maybe if I do another sorting video I can do that.
Hiii I have a question.
I have some code that uses a quadtree to power through some calculations. The quadtree appears to work fine, which is a positive. I load data in preload() from a json file, and sometimes the quadtree (which is in setup() ) begins building the tree prior to the data finishing its load. Which means all of my answers end up being wrong. Any idea why?
Would you mind asking at discourse.processing.org/! It's a better platform for Processing and p5.js related code questions. You can share code there easily! Feel free to link from here to your post.
Mate Im pretty sure the partition function is the sum of the Boltzmann distribution over all the microstates of the system.
I just listened to the @basecs podcast episode all about this!
Oh, hello there @Jonathan Cousins! How are things? I love that podcast, but haven't kept up, will have to listen now!
I need that thingy you blow in and it sounds like a locomotive, what is it called? :)
I don’t understand why you would need to recursively call quicksort for each half. I thought the partition function completely sorts the array so why cut it into half and do it again?
please make a sudoku solver or anything that uses a recursive backtracking algorythm. would becool :) thanks
drink everytime he writes or types "partion"
partition*
QuickStort
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)
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?
I think then it will become randomized quick sort, which is better in case of worst case.
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.
This workflow video series will help! th-cam.com/play/PLRqwX-V7Uu6Zu_uqEA6NqhLzKLACwU74X.html
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 ^_^ .
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
24:49 shouldn't this use states[i+start] again?
What about multithreading? Could you pick every 4 numbers and sort around those?
Sorting is really complicated in multithreading, youd be making 4 individual partition calls for no real reason. What you could do is, everytime theres a new quicksort call, send it to a new processor, or queue it on another one. The problem then becomes synchronization. If for some reason a faster processor reaches a part of the array much further down the recursion but the segment hes working on hasnt been executed by the other processor in charge of that call, then you dont end up with the correct sort
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.
Please also do a video for merge sort.
something else entirely but an idea for a coding challenge is a trie data structure visualisation
Please do a Processing version for this.
I dont know that async keyword :(
where/when do you do your streams? it'd be nice to watch one in real time
Right here on TH-cam subscribe and click the alarm bell for notifications 😀
Hey would it be possible to implement something like this in Processing (not p5) ?
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
You can do so, which would then be mergesort, not quicksort.
Bro, why you always use javascript in each coding problem?