Quicksort: Partitioning an array
Vložit
- čas přidán 15. 10. 2014
- This video shows how partitioning may be achieved, as part of the process of Quicksort. At the end of the partitioning process, the array is divided into two sub-arrays. One sub-array contains elements that are less than a chosen pivot, while the other contains elements that are more than the pivot. The partition function should return the position of the pivot.
Note:
While recording the video, I was focusing on moving the pivot to the (i+1)th position towards the end of the video, and in my hurry to finish the video, I had forgotten that a swap is sufficient. Agree (and this has been brought up many times in the past) that a swap at the last step is quicker and more efficient. However, it is not incorrect to shift - just inefficient. Actually, as mentioned right at the beginning, the objective here is to find the position of the pivot for the partition.
All the fancy power points and drawing tablets and still the best explanation is a homie with paper cups.
Thank you, sir!
I think it's funny how you don't use anything fancy to explain this, and yet your explanation is still one of the best.
Thank you. Glad you liked it :)
Not sure.. have you seen the Hungarian dancers?
Thank you for the thorough explanation!!
Its called being a good teacher
This is the best video on Quicksort.
However, at 4:05, we could just swap "Pivit" and the "i+1".
Yo I'm glad you said that. I was about to make a loop to shift them all (which would increase the time complexity). But your suggestion gives the same result (numbers to the right are larger than pivot) at a shorter time complexity
One of the most understanding videos i have seen so far about QuckSort. Thank you sir, extremely understanding
Glad you liked it
Understandable*
I watched your instruction twice, not because it's hard to understand but so enjoyable to watch. Thank you
Right!? I could not believe how simple he made it seem.
Usually I don't comment on video but I have to make an exception for this one because EVERYTHING WAS JUST PERFECTLY EXPLAINED....
It changes from the videos where the guy takes more than 10mn to explain it in a way that will confuse more
KEEP IT UPP 🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥
Thank you for the compliment. Glad you like the video.
This Legend is replying to comments even after 6 years.❤
I'm no "legend" - I'm just an ordinary academic at a university. Thanks for your message, though.
this explains a lot why "i" started at index -1. Thanks.
This is a clear explanation, but I'd avoid shifting the array at 4:07 and just swap the 4 and the 8 (that is, the element at the pivot position with the element at i+1) since it's much less work and it will also result in guaranteeing what we need: everything to the left of i + 1 is smaller than the pivot, everything to the right of i+1 is greater than the pivot, and the pivot is at i.
I thought the same, was surprised when he moved all the cups lol. Great video though! Super clear
Thanks both. This point has been discussed at length in the past. You may wish to read the video description. Thanks for watching!
not gonna lie, its the best video available for quicksort.
Oh wow, that's the best compliment! Thank you for watching.
This is the best explanation of quicksort I've seen on youtube and using simple paper cups of all things.
I've never seen such an amazing teaching method, thank you! This is gold
Thank you for the compliment!
Teacher took 40 mins. Book took 1 hour. This guy taught me in 10 mins.
you are very good at explaining this complex algorithm!
with your calmness it was very easy to follow you step by step.
you are the only one that actually helped me to understand :)
Great job! Thank you!
This should be the 'go to' video for quicksort explanation
possibly best video on CZcams to understand Quicksort.
Everyone just dry runs the algorithm - without clearly showing what's being done and why.
You won 'em all!
Thanks~ I'm glad it helped.
This is the best explanation i've come across!
Amazing explanation! Thank you, Thank you, Thank you :) Very clearly explained and the visual aids were amazingly helpful.
You're welcome. Glad the video is of use to you.
probably the best explanation of quick sort in so less time,one thing to say to understand this better you first go throuhh the video explain by mycodeschool channel and then watch this and you will see clearly how things are working here.
Hats off you sir!
Great job.....
Thanks for your kind words
This is amazing! Great explanation. I could not understand quicksort until you masterfully and elegantly demonstrated how the algorithm works.
Thanks for the very kind words. Happy to help!
Only after watching this video did I understand that the `i` only increments when a swap happens, in effect keeping track of where the pivot should finally rest. The best explanation I've seen on quicksort partitioning!
Thank you prof KC Ang. After so many days of confusion I finally got clear explanation from your video. Thank you for virtually sharing your knowledges!!
Glad it was helpful!
Please, can someone give all the humans, animals and plants as subscribers to this legend
Very flattered by your comment! Thanks for watching.
I find it really interesting how Quicksort as a sorting algorithm itself is intuitively quite simple but I've seen so many different methods for partitioning the array.
this was the best explanation of Quicksort in youtube
Thank you. Glad you liked it.
This is most certainly the easiest video to understand about partition. I literally am mad it's this easy haha!! Thank you so much!!! I definitely did NOT study this the day before my test :P
Thank you. I'm glad you find it useful.
This is the correct way every human being can get crystal clear understanding of hardest topic easily
Respect to great teacher like you sir
love & Respect from India
Thank you and glad that you found the video useful. :)
It looks like this guy knows how to teach, awesome vid.
Thanks :) I try my best ...
Best explanation ever.
Very clear and crisp explanation and the representation helps to literally visualize the problem.
Thank you !
this is by far the best explanation of quicksort so far after pouring through countless videos.
thank you for this video!! i love how you used the cups, it's so much easier seeing this happen in real life instead of a digital diagram/images on screen.
Glad it was helpful!
At 4:06 (when the partitioning is finished) there was a shift in the array which is very expensive, for the purpose of the quicksort I believe it'd be a more beneficial if you instead swapped the pivot with (i + 1)
I struggled fully grasping this concept of why this works, you explained it very well and made the click that when I look back I don't understand where my confusion came through. Thank you so much.
You're most welcome. Good to know that this video had helped you overcome your struggles.
You are honestly good . Ur way is the best way to explain this, dunno why people keep explain this by code, all viewer want to know is the idea to do q sort ans you did it well
Glad you liked it. Thank you so much 😀
I wish our college lecture had explained it this clearly. College is where we go to get grades; CZcams is where we come to learn. Thanks KC Ang.
thank you again, I have spent my day trying to learn quick sort and this video actually gave a clear understanding to a point I can implement code with no problem. Thank you !!!!
Thank you for watching this video and leaving a comment!
Amazing, short, easy explanation
Happy to note you find the explanation easy to understand
One of the best explanations, you nailed it
Thanks for the compliments!
I've been searching like a hour for a clear explanation. Thank you! You are a life saver.
This is the most clear explanation I have ever seen of the algorithm. Thank you so much.
Glad it was helpful!
Incredibly helpful. Textbooks and online articles handwaved over partitioning. Thank you for explaining this so well.
I went though so many videos. This is where I have understood the logic behind this algorithm very well. Thank you so much Master.
Thanks for the positive comment!
Great explanation! One thing to mention is, instead of shifting everything from i+1 to the right, you can just do a swap of A[i+1] and pivot, (4 and 8 in this case) which is probably more efficient.
The loveliest explanation of partitioning ever made.
Hats off to you man!
Best demonstration I have seen for quick sorts. I'm a visual learner and using real world objects really helped, not to mention the great instruction and organized narration.
the best explanation of quick sort thank you
Glad you liked it!
@@mtophir wish me luck bro, im going to face interview in this week 🙏
@@eucliwoodhellscythe4324 Good luck! All the best!
Agreed with previous person. The most clear description of Quicksort I've seen. Well done and thank you.
Thank you
Was having a lot of trouble understanding this algorithm until I stopped here and watched your video - now it totally makes sense! Thank you for taking the time to not only make the video, but to actually demonstrate the algorithm in physical form. It really helped me to learn much more concretely than any of the code snippets other tutorials were relying on.
It's amazing how much better this tutorial is than the other ones out there. Especially from a non-native English speaker. I applaud you.
at the last step you should swap not shift ... shifting means moving all the next objects and that would be with no purpose ... but swapping does the work simply with no extra efforts
+Amr Saber yup^
This is the first explanation that I understand immediately after I've watched it! Thank you so much! Greetings from Hungary :)
This is single handedly the best visualization of quicksort I've ever seen. Thanks for this!
That's a very nice compliment. Thank you!
This is the best explanation of Partitioning on CZcams. Thank you!
Thank you~ glad you liked it.
Wow...the way you used the cups for explaning the concept is so creative
I finally understood QuickSort(A[],first,last). Thank you very much. You video was very illuminating!
You're great sir. I was trying to understand quick sort from many days, but you made me understand the working of quick sort partition in less than 5 minutes. Thank you so much.
After going through so many contents and CZcams videos I finally found someone explaining the Quicksort in a very clear manner. Brilliant job KC...!👌
Glad it helped!
Watched so many quicksort videos but this one is the best. Thank you good sir !
Glad you liked it!
Just Awesome !!!! Crystal Clear !! Tried a few lectures!
This is GOLD!
👍❤️
Thank you so much! This is the only explaination I can understand. No those fancy graphic animation and music, no confusing complex definition and pesudo code, just a straight forward visual explanation. After I watched this, the pesudo code suddenly makes sense now.
You're welcome and thank you for the kind words.
I believ i see your video everytime i need to refresh about quick sort. Thank you. I may have seen it more than 15 times !
he explains complex stuff in a very plain way. What an illustration!
The best explanation of partitioning I have ever seen.
Glad you think so. Thanks!
You are an amazing instructor ... its is considered the best tutorial in quick sort algorithm
Thank you for watching and for acknowledging the effort!
This is the best explanation of Quicksort I 've come across anywhere. Cheers
Very smart implementation Mr. Ang!
This is the best video on quick sort I have watched . Thanks man for making this amazing video.
Thank you. Glad you liked it!
you make so much sense, the hardest part of quick sort is understanding the first passing of the partitioning function. Thank you
Hope the visualisation in this video has made "the hardest part" a bit easier to understand.
WOW, I MEAN WOW. This is the best explanation of the QuickSort I have seen. Not even AI help could have shown that. Thank you.
Wow, thanks!
Finally I know how QuickSort works. Thank you.
OMG, your explanation makes a lot of sense compared to other videos i've seen, NOW I GET IT>>>>>>>>>>>>>>>> THANKS
You're welcome!
The best part was that you actually pointed me to the fact the (i) pointer is initially at (low -1) and that it will not be out of bound because it will be incremented just before the first swap. Special thanks for that.
Wow! What a great instructor. This is brilliant. Thank you so much for the amazing explanation.
Amazing explanation!
Glad you think so!
The kind of teachers we students crave for!!....Thanks Sir
The video describes the basic unit of computation in the processing of quick sort algorithm. Very clear and beautiful!
Thank you so much for a simple and wonderful explanation of partition algorithm for QuickSort. Beautiful!!
I already know quick sort but came here for the awesome explanation 👏🏼 its real simple and cool.
Glad you liked it!
Best explanation ever of quicksort
Thank you, and thanks for watching.
I've been watching about 20 videos of quicksort, this is only one that explains the concept clearly
One of the beast explanation of partition. You can also select i (=j) at 1st position and increment after swap, final move swap pivot with i+1 Thanks
the best explanation on this type of sorting, thank you a lot !
Glad it was helpful!
The best example I have seen on the internet. Thank you Sir
That's a great compliment! Thank you.
thank u sir....this is the most clear explanation than most of other explanations of quick sort in the youtube.
One of the best simulations of the partition procedure, thanks for making this video :)
I hope to see more of your video.
Thanks
Best video I've seen yet... keep up the good work!
Thanks for posting this. I found it enormously helpful.
You're most welcome!
Thank you for your professionalism, Tom.
The only clear visual explanation I was able to find - thank you :)
I have to admit there is a lot of great videos out there for data structure and sorting videos, but loved this one!
Thank you so much for the compliment!
please make more videos like this coz it is easy to understand. Thank you sir. 🎉🎉🎉👍👍👍❤️
clever way of sorting the array and demonstrating how the i and j move through the loop together and make the pivot! Thank you so much for your efforts!!
So simple and elegant, straight to the point. Much better than those overdone graphics you see in other channels.
Thank you for the kind words!
Extremly well explained ! Very good video !
Very clear explanation! Wish all of my proffessors had this impact
Thank you for your kind words
Perfect. Wanted to refresh my memory and saw this. I knew I did not need to see any pseudocode or code but just wanted to understand the process. This was perfect.
I have been struggling for a few days to get a clear idea of quick sort and sir you have made it super clear. Thanks a lot, sir💜
May God always bless you:>
Happy to know that the video was helpful. All the best!
Great video, thank you so much. The book and examples made no sense, but this is a lot better than the examples online.
it's an awesome explanation that clarifies many subtle moments to implementation. and even more, this trick with the last step!! ahahaha! I wanted to scream about p->i+1. sure, you did it intentionally for better memorizing)) amazing lesson. thanks from russia
WOW, I watched green animation video, and was giving up on quick sort, and then watched your video and its as clear as day.
Glad it helped!
He explained in 5 minutes what other videos didn’t in 10-15 minutes. Best quicksort video I’ve seen
Thank you for your vote of confidence.