Quicksort Algorithm: A Step-by-Step Visualization

[@LUCAZAMA-or2dt]

It's been two hours searching for a decent quicksort explanation and came across this great video, consider taking the path of the teacher if you are not already into it. Much love

[@QuocDatPhung]

Thanks a lot Lucazama! You can find all of my CS videos like Quick Sort in the following link (don't forget to share with others and kindly subscribe!): th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@LUCAZAMA-or2dt]

@@QuocDatPhung do not worry about it, i have already done all of that

[@QuocDatPhung]

@@LUCAZAMA-or2dt Thanks so much!

[@jeremysmelley7143]

This is definitely top 2 quicksort videos i've watched. Highly underrated, this helped a lot, thanks!

[@QuocDatPhung]

Thanks Jeremy! Please kindly subscribe and share! You can find all of my Data Structure videos here: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@ConorLambert]

Absolute best video on Quicksort.
I was looking at other vids from people with millions of subscribers and nowhere near as good as this.
Thank you my good friend.

[@QuocDatPhung]

Thank you for your kind words Conor! Please kindly share with your friends and subscribe to support me ~ also you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@Bromon655]

I watched a lot of quicksort videos and this was the first one that clicked with me. Well done

[@QuocDatPhung]

Thanks a lot Bromon! You can find my other CS videos in this playlist: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@mm-en1rf]

I appreciate the video greatly, I went through 2 other quicksort videos and this was the only one of the three which I could easily comprehend.
I'll be sure to visit your other videos when it comes to understanding more comp sci content !!

[@QuocDatPhung]

Hey there I'm really glad you found it helpful! You can find all of my CS videos in the link below (don't forget so share with your classmates to help them too!) th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@oshawastaken]

This is by far the best explanation of quicksort on yt, thank you!

[@QuocDatPhung]

Thanks so much! Please kindly also check out my Merge Sort video: th-cam.com/video/ho05egqcPl4/w-d-xo.html

[@BubsGirl291]

My prof attempted to explain quick sort in class to us and I left very confused. This was so clear and easy to understand, thank you for helping it click in my brain! Kudos to you sir!

[@QuocDatPhung]

Thank you BubsGirl! I'm glad you like my explanation! If you know anyone who needs help with this class, kindly share it with them and also subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@InfinityOver0]

Subscribed. Brilliant video. I will again go over it again tomorrow in the morning, take notes and understand quicksort once and for all. Thank you Quoc Dat Phung, your explanation is brilliant.

[@ethanaustin_17]

After watching a bunch of videos I finally came across one that I understood!

[@QuocDatPhung]

Thank you Ethan! Please kindly share with your friends and subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@harrygray9887]

outstanding work amigo. I was expecting thousands of comments.

[@QuocDatPhung]

Thank you so much Harry! Please kindly subscribe and share with your classmates. It really means a lot. Also, if you like my Quicksort video, you might also like my 4 min Merge sort video: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@g.r.4372]

I was 100% from beginning to end. You're a great teacher.

[@QuocDatPhung]

Thank you G.R! Please kindly share and subscribe~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@MariusCiutea]

I can't believe how well explained this is! And I'll never understand why college professors seem incapable of explaining in such an easy to understand manner.

[@QuocDatPhung]

Thank you for your kind words Marius! Please kindly share and subscribe~ all of my CS videos are in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@KnochenMarkSaege]

I've watched a few videos on this topic, and this one helped me personally the most, by far. Thank you for taking the time to explain in detail every step that is necessary to achieve the wanted effect. Also, explaining how the code behind it works really helped me grasp the concept.
Thank you very much for your effort :)

[@QuocDatPhung]

Thanks so much KnochenMarkSaege! I'm really happy that you found my video useful! I have an entire playlist on Algorithms; you might also like my 3 min Merge Sort explanation: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@Developer-s6f]

Very clear and correct explanation. Thank you so much for making an effort to explain this the correct way!

[@QuocDatPhung]

Thank you! Please kindly share with your friends and subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@AliCrown]

Best video ever!
I was just watching those videos that have millions of views, and I didn't get the point of this algorithm, but after this video, finally, I got off the struggle of a week.

[@QuocDatPhung]

Thank you so much Ali! I'm glad you like my explanation! If you know anyone who needs help with this topic, kindly share it with them and also subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@khoadoan8966]

Bro, you're amazing, explaining the complex processes so easily. Haven't touched DSA for a long time, and then having to learn it all over again after being laid off is really hard for me as I'm not as young. You've just helped me understand fuzzy complex knowledge really really well. Thank you !

[@QuocDatPhung]

Thank you Khoa! I'm really happy to hear that! Pleased kindly share ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@khoadoan8966]

@@QuocDatPhungI’ll share it, and have a look at your playlist. Really appreciate your contents.

[@abramweigant2438]

I never leave comments, but this video was incredible; good job, man!

[@QuocDatPhung]

Thank you AbramWeigant! Please kindly share with your friends and subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@strawberriesandcream2863]

best quicksort video i've watched that helped me clarify the concept :) thanks!

[@QuocDatPhung]

Thanks so much Strawberries! I think you'll like my Merge Sort animation too! Please check it out here: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@JacobChencha]

That was a beautiful explanation!

[@QuocDatPhung]

Thank you Jacob! Please kindly share with your friends and subscribe to support me ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@EnjoyerOfBepis]

I don't understand why the worst case is O(N^2).
When we move LEFT and RIGHT until they cross each over, we do RIGHT - LEFT operations which is equal to the length of our subarray. And we do it twice for both parts (left subarray and right subarray).
For example, let's sort an array of length 100.
In the first call of our partition func, we do 100 iterations.
Then we split it into two subarrays and call partition func on both of them, which gives us 50 + 50 iterations.
Then again and again.
Total number of iterations:
100;
50 + 50;
(25 + 25) + (25 + 25);
((12 + 12) + (12 + 12)) + ((12 + 12) + (12 + 12));
(((6 + 6) + (6 + 6)) + ((6 + 6) + (6 + 6))) + (((6 + 6) + (6 + 6)) + ((6 + 6) + (6 + 6)));
(((((3 + 3) + (3 + 3)) + ((3 + 3) + (3 + 3))) + (((3 + 3) + (3 + 3)) + ((3 + 3) + (3 + 3))))) + (((((3 + 3) + (3 + 3)) + ((3 + 3) + (3 + 3))) + (((3 + 3) + (3 + 3)) + ((3 + 3) + (3 + 3)))));
((((((1 + 1) + (1 + 1)... and so on
Sum of every row it gives us about ~650 iterations.
Calculation are very silly and simple, but the time complexcity seems always O(N*logN) for me, not O(N^2).
O(N*logN): 100 * 10 = 1000
O(N^2): 100 * 100 = 10000
~650 is closer to 1000.
Where am I wrong?

[@QuocDatPhung]

I know what you mean. In Computer Science sometimes you have to look at the proof of Quick Sort where they do a lot of math and get O(n^2). I remember when Iearn algorithms like Djkstra's and the run time is very unintuitive. The math in the proof is what determines it. After the Data Structures course, you'll likely be taking Analysis of Algorithms where they'll talk more about it. But for now just know Quicksort is O(n^2)

[@EnjoyerOfBepis]

@@QuocDatPhung Yeah, thank you for the answer. I found my mistake. The worst case when we divide an array not to 50 + 50, but 99 + 1. Then 98 + 1. Then 97 + 1. So total number of operations is 100 + 99 + 98 + 97 + ... + 3 + 2 + 1, which can be simplified to 100 + (99 + 1) + (98 + 2) + (97 + 3) + ... + 50 = 100 * 50 + 50 = 5050 operations. So it's closer to O(N^2).

[@QuocDatPhung]

@@EnjoyerOfBepis That's awesome! If you know anyone who needs help with this topic, please kindly share it with them and also subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@EnjoyerOfBepis]

@@QuocDatPhung Sure I'll do! Many thanks for your channel, it's extra helpful!

[@anooshiepooshie]

I love you bro. Everything made sense.

[@QuocDatPhung]

Thank you Anooshiepooshie! I'm glad you like my explanation! If you know anyone who needs help with this class, kindly share it with them and also subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@annarankin9103]

Thank you Quoc, this video has been very helpful.

[@QuocDatPhung]

Thank you Anna! Please kindly share with your friends (it means a lot) ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@st-lucia]

Thank you!

[@QuocDatPhung]

Thanks so much, St-Lucia - Castria La Patria! Please kindly subscribe! You can find the rest of my Algorithms videos here: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@FilhosdeAdao1]

Thank you. Best explanation

[@QuocDatPhung]

You're welcome! You can find all of my CS videos in this playlist (don't forget to share and kindly subscribe!): th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@ananthaprasetya3263]

Hi sir, why we need to swap array L and R with the same index? both already the same value.. Thanks

[@QuocDatPhung]

The algorithm will still swap them even though they are the same :)

[@stormShadow64]

awesome video, very clear

[@QuocDatPhung]

Thank you! Pleased kindly share and subscribe~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@hoteny]

Why do you continue when L

[@QuocDatPhung]

If you stop when they are equal, quicksort will not be able to handle duplicates in the array. For example, let's say the array is [4, 3, 5, 5, 5, 2, 1]. If your pivot is 5 and you stop the partitioning process at L

[@romanvolosiuk3919]

It really helped me. Thanks!

[@QuocDatPhung]

You're very welcome Roman Volosiuk! Please kindly subscribe! You can also find the rest of my Algorithms videos in this playlist: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@samuraijosh1595]

Hey thanks for the video, quick and to the point with nice visuals but how is space complexity O(log n)???

[@QuocDatPhung]

You're very welcome Doremon! The space complexity depends of where you choose the pivot. I wouldn't worry too much about it. You can find all of my CS videos in this playlist below (don't forget to share and kindly subscribe!): th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@samuraijosh1595]

@@QuocDatPhung never mind I learnt that it was the stack space, log n function calls in the stack. Since quick sort is hyped up as in place sorting, I just assume constant space. Tbf, I've seen leetcode questions where it was advised to just ignore the recursion function stack space and treat the whole thing as if it was constant space. A bit inconsistent...

[@QuocDatPhung]

@@samuraijosh1595 Thanks for letting me know!

[@Harshavardhan-pk3pk]

good explaination must watch

[@QuocDatPhung]

Thank you! Pleased kindly share and subscribe~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@aleareyatol]

How about if there is a 9 elements, is it still the same process?

[@QuocDatPhung]

Yes, the process will be the same

[@awieeeee]

hello, what if the mid index results in a decimal value? what number should i choose?
the values are (5,1,8,4,3,9,6,2), so
mid index:
m = 0 + 7 / 2 = 7/2 or 3.5
where should the pivot be placed?

[@QuocDatPhung]

The formula for calculating mid at 0:25 has the floor sign (meaning to round down). So if m =3.5, we simply round down to 3. Let me know if that makes sense! You may also like my Merge Sort video :)

[@phoenixkomben-ie9xq]

Great video

[@QuocDatPhung]

Thank you Phoenix! I think you'll like my other Sort videos too! Don't forget to share with your classmates and kindly subscribe ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@yaelw5986]

does this method use hoare's partitioning

[@QuocDatPhung]

No I don't think so. I hope you enjoy this video! If you do, you might also like my Merge Sort video too: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@coryanders6328]

easily the best video i've seen on this. all the other ones give very poor, if any, explanation as to what they are doing

[@QuocDatPhung]

Thanks so much Coryanders! You'll probably like my 3min Merge Sort video as well: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@TungNguyen-oi4xo]

cảm ơn e, giảng rất dễ hiểu

[@QuocDatPhung]

Cám ơn anh! Em có làm clip về Merge Sort và các algorithms khác ở đây nè: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@LizyAd]

Searching for a good video on quick sort has been difficult but this is very good. Thanks

[@QuocDatPhung]

Thank you Lizy! I'm glad you like my explanation! If you know anyone who needs help with this topic, please kindly share it with them and also subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@lowe7372]

Best explanation, and best mindset to approach the algorithm. The game example is AWESOME. Thank you very much! please do more

[@QuocDatPhung]

Thank you very much! I have an entire playlist of my Algorithms; I hope you'd enjoy my Merge Sort video as well: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@naza2105]

trank you so much

[@QuocDatPhung]

You're welcome Naza! Please kindly subscribe if you enjoyed! Also, you can find all of my Algorithms videos here: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@thuhuynh7474]

Anh nhìn xịn quáaaa

[@QuocDatPhung]

Hehe cám ơn em! Tất cả clip máy tính của anh nằm trong link sau đây (em đừng quên chia sẻ và đăng kí ủng hộ anh nhé!): th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@hasanshahriarboni7957]

❤

[@QuocDatPhung]

Thanks very much Hasan! I hope you will also enjoy my Merge Sort video: th-cam.com/video/ho05egqcPl4/w-d-xo.html

[@samirpandit8899]

the goattt

[@QuocDatPhung]

Thank you SamirPandit! Please kindly share with your friends and subscribe to support me (it means a lot) ~ you can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@prashantnegi6831]

can anybody reply with python code for this?

[@prashantnegi6831]

don't worry, wrote it in java with the help from your python code, thanks

[@QuocDatPhung]

You're very welcome! You can find all of my CS videos in the link below (don't forget to share with your classmates!): th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html

[@amazekhashaa7309]

How did you maintain happiness in your face long time

[@QuocDatPhung]

Haha I enjoy the process of making videos :) You can find all of my CS videos in this link: th-cam.com/play/PLeTO6OT3-FKmuxOu4RtupTay1yrMp6QGC.html