Quicksort: Partitioning an array

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.

[@whoopdeedoodude]

All the fancy power points and drawing tablets and still the best explanation is a homie with paper cups. Thank you, sir!

[@diegod.8518]

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.

[@mtophir]

Thank you. Glad you liked it :)

[@nadavsam]

Not sure.. have you seen the Hungarian dancers?

[@hernancedillo6144]

Thank you for the thorough explanation!!

[@bipdopbop1878]

Its called being a good teacher

[@srishtiavalakki751]

One of the most understanding videos i have seen so far about QuckSort. Thank you sir, extremely understanding

[@mtophir]

Glad you liked it

[@zingg7203]

Understandable*

[@justdanaus]

I watched your instruction twice, not because it's hard to understand but so enjoyable to watch. Thank you

[@nkosinathindlovu3059]

Right!? I could not believe how simple he made it seem.

[@conea6891]

This is the best video on Quicksort. However, at 4:05, we could just swap "Pivit" and the "i+1".

[@crazguykwan8955]

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

[@aaryaveerrajput8031]

This Legend is replying to comments even after 6 years.❤

[@mtophir]

I'm no "legend" - I'm just an ordinary academic at a university. Thanks for your message, though.

[@namanaggarwal5417]

not gonna lie, its the best video available for quicksort.

[@mtophir]

Oh wow, that's the best compliment! Thank you for watching.

[@21void5]

this explains a lot why "i" started at index -1. Thanks.

[@shikha125]

I've never seen such an amazing teaching method, thank you! This is gold

[@mtophir]

Thank you for the compliment!

[@bogslut]

This is the best explanation of quicksort I've seen on youtube and using simple paper cups of all things.

[@fodecissokho9918]

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 🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥

[@mtophir]

Thank you for the compliment. Glad you like the video.

[@angelamunyao7877]

This is the best explanation i've come across!

[@mapmappampam8758]

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!

[@washboy]

This should be the 'go to' video for quicksort explanation

[@estefaniac8260]

Amazing explanation! Thank you, Thank you, Thank you :) Very clearly explained and the visual aids were amazingly helpful.

[@mtophir]

You're welcome. Glad the video is of use to you.

[@adilbaig7022]

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!

[@ChrisLeeX]

Incredibly helpful. Textbooks and online articles handwaved over partitioning. Thank you for explaining this so well.

[@sankalparora9374]

possibly best video on KZbin to understand Quicksort. Everyone just dry runs the algorithm - without clearly showing what's being done and why. You won 'em all!

[@mtophir]

Thanks~ I'm glad it helped.

[@zoriiginalx7544]

This is amazing! Great explanation. I could not understand quicksort until you masterfully and elegantly demonstrated how the algorithm works.

[@mtophir]

Thanks for the very kind words. Happy to help!

[@Mr.SuperMan]

The loveliest explanation of partitioning ever made. Hats off to you man!

[@fcsie]

this is by far the best explanation of quicksort so far after pouring through countless videos.

[@nightfox6738]

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.

[@qaipak1]

Teacher took 40 mins. Book took 1 hour. This guy taught me in 10 mins.

[@peterbalogh5622]

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.

[@jimmyfl0]

I thought the same, was surprised when he moved all the cups lol. Great video though! Super clear

[@mtophir]

Thanks both. This point has been discussed at length in the past. You may wish to read the video description. Thanks for watching!

[@JaBoss397]

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 !!!!

[@mtophir]

Thank you for watching this video and leaving a comment!

[@sakumas1183]

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.

[@mtophir]

Glad it was helpful!

[@katrinejensrud537]

this was the best explanation of Quicksort in youtube

[@mtophir]

Thank you. Glad you liked it.

[@chtr33]

I've been searching like a hour for a clear explanation. Thank you! You are a life saver.

[@samuelvalentine7846]

Please, can someone give all the humans, animals and plants as subscribers to this legend

[@mtophir]

Very flattered by your comment! Thanks for watching.

[@ibotah]

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

[@mtophir]

Thank you. I'm glad you find it useful.

[@karimp59]

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!!

[@mtophir]

Glad it was helpful!

[@rew23able]

Best explanation ever. Very clear and crisp explanation and the representation helps to literally visualize the problem. Thank you !

[@igorf243]

It looks like this guy knows how to teach, awesome vid.

[@mtophir]

Thanks :) I try my best ...

[@01binaryboy]

I went though so many videos. This is where I have understood the logic behind this algorithm very well. Thank you so much Master.

[@mtophir]

Thanks for the positive comment!

[@billbez7465]

Agreed with previous person. The most clear description of Quicksort I've seen. Well done and thank you.

[@mtophir]

Thank you

[@Honest_Reply900]

One of the best explanations, you nailed it

[@mtophir]

Thanks for the compliments!

[@hidroklorotiazid]

This is the most clear explanation I have ever seen of the algorithm. Thank you so much.

[@mtophir]

Glad it was helpful!

[@prashantgupta808]

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.....

[@mtophir]

Thanks for your kind words

[@-kindredeternalhunter9907]

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

[@mtophir]

Glad you liked it. Thank you so much 😀

[@DataStructures]

Amazing, short, easy explanation

[@mtophir]

Happy to note you find the explanation easy to understand

[@BrandNewByxor]

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.

[@andrewkaram6733]

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.

[@mtophir]

You're most welcome. Good to know that this video had helped you overcome your struggles.

[@JasonJason210]

I wish our college lecture had explained it this clearly. College is where we go to get grades; KZbin is where we come to learn. Thanks KC Ang.

[@nebula1100]

This is single handedly the best visualization of quicksort I've ever seen. Thanks for this!

[@mtophir]

That's a very nice compliment. Thank you!

[@courses-lectures]

You are an amazing instructor ... its is considered the best tutorial in quick sort algorithm

[@mtophir]

Thank you for watching and for acknowledging the effort!

[@spioboy1]

This is the best explanation of Partitioning on KZbin. Thank you!

[@mtophir]

Thank you~ glad you liked it.

[@Moch117]

Watched so many quicksort videos but this one is the best. Thank you good sir !

[@mtophir]

Glad you liked it!

[@kylefang8254]

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.

[@mtophir]

You're welcome and thank you for the kind words.

[@marcelcohen4844]

I've been watching about 20 videos of quicksort, this is only one that explains the concept clearly

[@emeryli2331]

he explains complex stuff in a very plain way. What an illustration!

[@Bestcuriosity_1]

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

[@mtophir]

Thank you and glad that you found the video useful. :)

[@sudheerkaneti203]

thank u sir....this is the most clear explanation than most of other explanations of quick sort in the youtube.

[@JaBoss397]

you make so much sense, the hardest part of quick sort is understanding the first passing of the partitioning function. Thank you

[@mtophir]

Hope the visualisation in this video has made "the hardest part" a bit easier to understand.

[@eucliwoodhellscythe4324]

the best explanation of quick sort thank you

[@mtophir]

Glad you liked it!

[@eucliwoodhellscythe4324]

@@mtophir wish me luck bro, im going to face interview in this week 🙏

[@mtophir]

@@eucliwoodhellscythe4324 Good luck! All the best!

[@amrsaber5457]

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

[@jogofwar99]

+Amr Saber yup^

[@memeingthroughenglish7221]

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!!

[@mukul98s]

This is the best video on quick sort I have watched . Thanks man for making this amazing video.

[@mtophir]

Thank you. Glad you liked it!

[@giovannicarovanello62]

I finally understood QuickSort(A[],first,last). Thank you very much. You video was very illuminating!

[@AlexRyaguz]

The best explanation of partitioning I have ever seen.

[@mtophir]

Glad you think so. Thanks!

[@pastafarian8410]

This is the best explanation of Quicksort I 've come across anywhere. Cheers

[@excelsior759]

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 !

[@prashasthapaduri4425]

Wow...the way you used the cups for explaning the concept is so creative

[@sonofage]

OMG, your explanation makes a lot of sense compared to other videos i've seen, NOW I GET IT>>>>>>>>>>>>>>>> THANKS

[@mtophir]

You're welcome!

[@bilalkhanthedreamer]

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.

[@ThePr0Br0]

I'm crying, you have successfully beaten my top ranked uni professors. Perfect explanation

[@kevinvira]

Finally I know how QuickSort works. Thank you.

[@Rliu1992]

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.

[@yolamontalvan9502]

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.

[@mtophir]

Wow, thanks!

[@danielwang4904]

You just did an explanation that is better than any of my professors. THANK YOU!!

[@sulaymonolimov7798]

Amazing explanation!

[@mtophir]

Glad you think so!

[@crepkey]

This is the first explanation that I understand immediately after I've watched it! Thank you so much! Greetings from Hungary :)

[@indubitablewordsmith9138]

He explained in 5 minutes what other videos didn’t in 10-15 minutes. Best quicksort video I’ve seen

[@mtophir]

Thank you for your vote of confidence.

[@kk-ol7nw]

I surprised that so many people in KZbin do not understand how the quicksort works even if they post the video about it. Except for him. great video.

[@i2Chinese]

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)

[@leahwilson5471]

Best video I've seen yet... keep up the good work!

[@MrChazmond]

So simple and elegant, straight to the point. Much better than those overdone graphics you see in other channels.

[@mtophir]

Thank you for the kind words!

[@dewittli7570]

best explanation of the algorithm, cleared my confusion in minutes. thank you!!

[@anujagulhane8543]

The kind of teachers we students crave for!!....Thanks Sir

[@jogofwar99]

Very smart implementation Mr. Ang!

[@user-tz7vl4no6o]

The video describes the basic unit of computation in the processing of quick sort algorithm. Very clear and beautiful!

[@user-mj1lu4cl1j]

After going through so many contents and KZbin videos I finally found someone explaining the Quicksort in a very clear manner. Brilliant job KC...!👌

[@mtophir]

Glad it helped!

[@akhilsanker2681]

Just Awesome !!!! Crystal Clear !! Tried a few lectures! This is GOLD! 👍❤️

[@zoltanbiro6388]

Best explanation ever of quicksort

[@mtophir]

Thank you, and thanks for watching.

[@amadousallah6634]

Wow! What a great instructor. This is brilliant. Thank you so much for the amazing explanation.

[@farhadpagdiwala1789]

Thank you so much for a simple and wonderful explanation of partition algorithm for QuickSort. Beautiful!!

[@Julian-tg3iq]

Thank you so much, my prof. didnt explain it as good as u did, i was really confused about the pivot before.

[@mtophir]

Glad it helped!

[@m16averick]

Very clear explanation! Wish all of my proffessors had this impact

[@mtophir]

Thank you for your kind words

[@harryc5097]

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.

[@buraiden917ify]

Thank you very much. This video was very helpful in understanding the PARTITION algorithm.

[@n00byscrazycorner43]

Great video, thank you so much. The book and examples made no sense, but this is a lot better than the examples online.

[@blackmamba9950]

The best example I have seen on the internet. Thank you Sir

[@mtophir]

That's a great compliment! Thank you.

[@kentnixon1651]

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.

[@shivanshudwivedi9001]

He is probably the simplest man on internet! Thanks man! appreciate it.

[@globnomulous]

Thanks for posting this. I found it enormously helpful.

[@mtophir]

You're most welcome!

[@jadenataylor]

First video of 5 that actually made sense

[@mtophir]

Thanks.

[@SaurabhKr]

One of the best simulations of the partition procedure, thanks for making this video :) I hope to see more of your video. Thanks

[@GHB775]

definitely the best explanation to be found on youtube. Thank you!

[@brahmdeepsingh5246]

I already know quick sort but came here for the awesome explanation 👏🏼 its real simple and cool.

[@mtophir]

Glad you liked it!

[@vlads7774]

the best explanation on this type of sorting, thank you a lot !

[@mtophir]

Glad it was helpful!

[@thomasgericot9997]

Thank you for your professionalism, Tom.

[@nanzownzu]

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.