The Quicksort Sorting Algorithm: Pick A Pivot, Partition, & Recurse
Вставка
- Опубліковано 28 вер 2024
- Code & Problem Statement @ backtobackswe....
Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers: offerfeed.io
Join Our Coaching Service: backtobackswe....
Question: Implement QuickSort. Explain how it works. Explain the best and worst cases.
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
Table of Contents:
Talking About Stuff 0:00 - 1:05
Introducing Quicksort 1:05 - 2:04
The Split Subroutine 2:04 - 2:43
The Partition Subroutine 2:43 - 3:24
Partitioning: Choosing A Bad Pivot 3:24 - 10:34
Partitioning: Choosing A Good Pivot 10:34 - 15:11
Analysis: Choosing Bad Pivots 15:11 - 19:06
Analysis: Choosing Good Pivots 19:06 - 22:07
Analysis: Good Pivots - Work Done At Leaf Level 22:07 - 23:37
Flashback To Merge Sort 23:37 - 24:01
Why Quicksort Is O(n*log(n)) 24:01 - 25:02
Wrap Up 25:02 - 26:12
Errors:
3:25 - 15:11 -> I messed up how I advanced 'i' in both examples. I should have started 'i' at left - 1 everytime...my bad. What should happen is that we should start 'i' at 'left - 1' and anytime we swap into 'i' we always advance 'i' FIRST before the swap. These errors don't change the fundamental job of 'i', which is to keep the tail of the section of items less than the pivot. Make sure you take that away from this.
4:02 -> Forgot to edit that text out haha
24:23 -> This is only the exact bound on the best case. Not the average case as well.
The code for quicksort is in the description. Fully commented for teaching purposes.
This guy's : is this ever impacting u?
Me : what? It's saving my life
great lol
It's impacting. In a good way. Most professors in most cs programs really don't go into detail about these algorithms much. Even grad school programs have that problem at times because then it seems like you should know these things. You're doing a good job and hopefully this channel and others stick around.
One of the best Tech -tuber, has an website on interview prep and still gives his best in youtube explanantions and dont advertise his website on youtube like tech lead , clement does,
tech-lead and clement should learn from him on how to give best in youtube and stop honeytrapping vulnerable kids
thx
tech lead is a psychopath lol
A CS tutor that speaks clearly and concisely??? Very rare!
yeah
Jonathan Banuelos you mean he doesn’t speak Indian accent lol
@@alanliang9538 what do you mean by that??
@@pulkitjain8135 racism
@@BackToBackSWE Are these bot replies? Why are most of your replies so bland and short
Impact ?? it's life saver.... when ever i get stuck on some basic concepts ..this is the place i jump to... keep up the good work.
hahaha thanks, yeah I'm back, about to make a ton of videos
Hey man thanks for posting these videos they are helping me a bunch, I'm about a month out from my job hunt, using your videos to prep while I continue to learn some Angular. Going to pitch in what I can for the Patreon thanks again !!!
Aw, thanks
Hey Man i am also in the same position with Algo and Angular but i think i am comfortable with Angular, Do you want to study together ?
"We do not place an item, into the section, that is less than the pivot." - just needed that much.
Thank You, Brother! #keepUptheGoodWork.
You are my favorite! What is really helpful is that you explain the idea, which is what a lot of videos don't do. Mosts just focus on the coding, but not in the concepts. I'm very thankful I found you!
great and glad you're here.
This guy is a genius, find an easy and intuitive way to explain.
For sure your videos is causing a positive impact. At least, for me this channel is so valuable. Great job man!
This is the only vedio I found which tells exactly what exactly is PIVOT.. THANKS
BRO
sure...bro.
Hey, my friend. I'm an SDE with a couple of years of industry and academic background. I really appreciate your effort to explain this algorithm. Regardless of the commercial purpose behind the video, your explanation is mostly accurate and easy to understand ( Though I have to say, it's better for you to put the average case before the worst-case example in this video.) Carry on, looking forward to new content from you!
btw: I have the confidence to say many, yes many, explanations of quicksort from some others are WRONG. Well done, sir!
one more suggestion, I will be better for you to explain why quick sort is "Quick". I know the answer..but..I'll leave the work to you...
I haven't understood quicksort for 2 years, thanks a bunch man
thanks for watching
Wonderful tutor! With each passing days, I am falling in love with Algo's, good job brother..looking forward to have more lessons from u.
great to hear.
I guess you have not enough subscribers and watches! One of the best CS videos I ever seen. Thank you!
we coolin', in time
Yet another great video. Where were you when I was learning this stuff in undergrad? :-)
In middle school I think...near corn fields 🌽🌽
why is this guy better than the lecturer in my course that I paid $2.2k for?
im not sure
I wish i could like the video million times. Thanks for the gift.
sure
ı hated data structures lectures before thıs man but now I can easily understand everythıng .thank u a lot .You are my hero :)
Happy Holidays 🎉 this means so much, thanks, songulmesale! We'd love to offer you a 40% Off our exclusive lifetime membership just use the code CHEER40 - backtobackswe.com/checkout?plan=lifetime-legacy&discount_code=CHEER40
It's glad to see that my favorite basketball player Chris Paul teaching the algorithm courses.
You're very good at explaining. I watch your videos and they make me very happy
Excellent explanation of Lamuto partitioning
Your videos are really awesome and have helped me alot in my data structures class for LSU. Thank You!
sure
You explanation is amazing. be assured that one day I will take few days off to watch all your algorithm themed videos :)
thanks and nice
Love the video, but isn't there a more optimized way to implement quick sort? In the code, it always picks the last item as the pivot, which is some cases with large inputs, it will timeout.
6:11 - "what does I do?"
Good fucking question
Any new videos? Your explanation is so good!
great video. Could you please make a video for Subset Sum Problem (Print all subsets with given sum) Dynamic Programming?
maybe
YOU ARE HAVING AN IMMENSE IMPACT. AND THANKS FOR IT!!!
thanks haha
This channel made me love algorithms again
ye
Best content I have ever encountered
thx
@@BackToBackSWE you really read your comments. Only some have this quality.
Really Impressed
@@saurabhjindal2775 Yeah haha, why wouldn't I. I really care about what I'm building.
The more sorting videos I watch, the more unsorted my brain becomes.
man I love your videos, your teaching skills are amazing!
You are a real man
im normal
This is so well presented. Instant subscribe. Thanks man.
Does this implementation use the Hoare partition scheme?
im not sure what that is
@@BackToBackSWE Thanks for this video and for replying. I don't know what it is either, which is why I asked. Apparently there are two common ways to partition: Lomuto's way or Hoare's way. en.wikipedia.org/wiki/Quicksort#Hoare_partition_scheme
No. This one is Lomuto's partition scheme when you have two pointers (i and j) starting from the beginning.
Hoare's partition is when we have two pointers: one starts from the beginning, second starts from the end.
Looks like Hoare's partition is more preferable cause it makes 3 times less swaps than Lomuto's in average.
cs.stackexchange.com/questions/11458/quicksort-partitioning-hoare-vs-lomuto
www.geeksforgeeks.org/hoares-vs-lomuto-partition-scheme-quicksort/
I asked myself the same question because there are different ways of quick sort implementation and they really differ. So it was a bit confusing for me at first why I see the same algorithm and different ways to implement it.
@@snoopaku Thanks!
Subscribed! Very good explanations, please continue doing what you do.
thx
Amazing video! listen you are something special. I really wanted to open a youtube channel about computer siecne and programming in my native language(Hebrew - I'm from Israek :) ), and you really inspire me to actually try and do that.
Thank you for everything!
You can do whatever you want. This all took about 1.5 years so like...if you believe and the world has the need for it you will succeed. Like srs.
Does anyone understand how 17:32 worked? I would have thought the summation would be the sum n-i from i=1 to n-1. This is due to the pattern of seeing n-1, n-2 , n-3 on each level and needing to add them all together
This seems to be a mistake but I don't remember the math from this video too much. I was going straight from notes I took before the video so not sure what I was on about. It still would be quadratic comparisons: imgur.com/a/MWQOBkd. Can you affirm this was a mistake? Then I can update the pinned note to point it out. Thanks!
@@BackToBackSWE No problem at all, so sorry for the late response was so deep into algos study that I never looked at UA-cam until I finished my exam yesterday! The maths checks out. If you think about it the sum of (n-i) for i incrementing all the way to n does just equal the sum of i. For instance, let n be 5 and i = 0 and lets follow the (n - i = val) format. (5 - 0 = 5) + (5 - 1 = 4) + ... + (5 - 4 = 1) Which is the same as 0 + 1 + ... + 5. I hope that cleared that up, thanks for making this content, I absolutely love your videos and will continue to subscribe even beyond algos class :)
best explanation on quick sort !!
thanks
Such a great explanation
love you sooo much, this video really helps!!!
sure
Thanks man,good explanation.
sure
Lol doesn't the array already have to be sorted in order for you to find the optimal pivot (which is the median)?
no/yes - and yes that's the idea, picking a good pivot is...pivotal...to how the algorithm performs.
How can you understand so much when you are so young?
Hey man thanks for the videos
sure
You are awesome dude
Thanks!
sure
Well explained thanks 😊
sure
Your vids are amazing
Thank you so much. Your video helps me a lot, I am a CS student in SBU right now :D.
sure
Thank you so much
1:15-Quicksort
How are you doing lately
pretty good
Came for the code. Stayed for the sandwich
nice
bessttessttt ever suppp nicely explained Quicksort
hey
I need to give you Money
0:02
what did I do
@@BackToBackSWE It's been a while since you've done a video lol
why is hamilton teaching sorting algoriyhms
I wish I just watched your videos instead of taking my algorithms and data structures class
ye
Hey man. Been watching your videos for a few weeks. Your explanations and thought process is exactly what I needed to get a refresher on all things ds&a. I just recently landed a job offer at a dream company, so thanks a ton for all your hard work and help!
nice. Hope work goes well and you are happy :)
My feeling is also same here, Iwas searching for this kind of thinking ability
dude you're literally the only reason why I understand these algorithms. My CS 101 prof teaches so weirdly, you should really consider pursuing academia if you haven't already
thanks and I do not want to
@@BackToBackSWE relatable LOL
@@BackToBackSWE lmao
Amazing Videos ! I love how you explain everything at the deepest level which is exactly what I need to understand those algorithms properly :D
great
2022 and you're still helping people. I'm not enjoying my classes but watching your videos give me reassurance that I really like these topics. Thanks a lot man!
Glad to hear that! Subscribe to our DSA course with a flat 30% discount for some amazing content b2bswe.co/3HhvIlV
now we are at 161k
thank you for all your efforts
love from india
I've never understood something so clear... thank you so much! :')
nice!
FINALLY someone who explains what a pivot is. Pivot concept is key to understand how quicksort works and also to understand "the kth largest element in an array" problem.
yes
Dude. Thank you for putting the time in making these videos. They are IMMENSELY helpful! Don't burn out making them, take your time, do them at your pace, cause they are some of the best in the business. Really, you are awesome.
Thanks. I haven't burnt out. I just started work in San Francisco and I am building a pretty cool and fancy site for this channel which I hope to launch mid-end of July. Once it is out I'll be back on the throttle to post more technical videos as I support the site and begin working on the next software.
Don't stop doing what you're doing! These videos have been an incredible help in getting my head around algorithmic time complexity for my computer science masters - thank you!!
Hey Bro.... Just wanna say... Keep up with your videos, they help students like us all around the globe..... ❤️❤️❤️❤️❤️❤️
hah nice!, wassup
partition partition partition...all I can think about is Beyonce. RIP my coding interview
yes
You're one of the most eloquent tech guys on youtube. I just started programming this month, and your video helped me implement quicksort in JS!
great! but im not a tech guy, Im just a guy
give this man a gold metal! respect!
thanks
This is one of the Back to Back SWE videos have helped me understand "Introductions to Algorithms" - a book probably aimed at people who already understand the algorithms in question. I am so glad for this series. Thanks a lot!
great
Thank you so much,you probably dont know how much this means to me. Love from india🇮🇳
sure and thanks
At 10:38, you say that it doesn't matter where i starts; as far as I saw the algorithm says it's got to start at start - 1, which de facto makes all the passes in the first iteration to swap i with j, but all instances of i and j are equal (that's cause you increment the i before the swap), or the condition about array[j]
ok
6:10
"what does i do?" - me trying to learn DS&A before @Back To Back SWE
cool a brother
Thanks for hard work, I can see how much effort you put in this video.
ye
this black life matters
lol - we are all human, no colors
Teaching is an art and you are an artist :)
yis
"The code's in the description." Not any more 😢
the repository is deprecated - we only maintain backtobackswe.com now.
10:50 : Why "pun not intended"? Intend your puns. This was a good one, btw.
hahahaha what did I say
I'm sorry but I think your video is incorrect from around 12:00. You need to increment i first and then swap. Just like in your code. Cuz if you do it how you showed for example if we have 4 5 8 3 9 7 and we have i and j on 4. Then we move j one and what you said we need to swap 4 and 5. then i and j on 4 again now moved 1 forward. then we move j to 8 nothing happend move it to 3. we need to swap it for 4 which makes no sense THEN move i? No, your code is correct though :D And thank you for the explanation of the time complexity.
Ok, heh, I can't verify that (busy) and ok noted
The example at 11:00 can be more helpful if it has a number in the first half that is greater than the pivot, for example [3, 8, 4, 5, 9, 7] and pivot is 7. when i = 0, j = 1, we don't do the swap since 8>7, then j becomes 2 and based on your description we swap 3 and 4? What about 8 in between them? It should not stay where it is
ok
the 8 is going to get pushed back
One of the best instructors on UA-cam! Thank you for your contribution!
where is the code for this. Cant find it in the description
The repository is deprecated - we only maintain backtobackswe.com now.
cannot find the link in the description to the code you mentioned in the video?
The repository is deprecated - we only maintain backtobackswe.com now.
It is really much helpful and good then our professor lectures
thx
Hey bro, can you do an average case analysis for quick sort with mathematical induction.
I cannot but would if I had the time allocation and if it was rewarding enough from an angle of benefiting the whole viewerbase , etc.
Stumbled upon this during my interm. algorithms class at UC Riverside. Honestly dude, your short videos do more than entire lectures for my understanding. Thank you.
tbh miss you speaking passionately loud ahah it got me PUMPED TO LEARN but thank u always for these
hahahaha, I HATED that era of this channel. I wish I could erase it but the content is still decent. So I left it.
I've been impacted
hahaha what
Hay man I just want to say thanks for all the videos because of that today I am having f2f interview in Amsterdam. I am not sure I will pass or not but you gave me enough confidence to face it.. :) cheers
Hahaha nice! I just came back from Amsterdam...like 2 days ago. That's wild. I walked past the Oracle office behind this one Dutch dude who was speaking Dutch and he had a cool Oracle bookbag.
Ahhh...good times.
@@BackToBackSWE Ohh I missed my chance of doing mock interview with you :p
@@jageenshukla4825 haha
Thanks for this, I was actually wondering couple days ago why there isn't a sorting video for quick sort.
yeah, give me a year or 2, this channel needs to be fleshed out more. I'm aware of all that's missing for the most part.
How log(100000)base 2 is calculated
you can google that
Hey bro , your videos are really helpful. Thanks for doing this. I notice(think) there is small difference between your explanation in video and code. As per your video , if J < pivot , then we need to swap the i with J and then increment I. This is not working for dataset (1,2,1,2). However when I check the code. Algorithm is if J < pivot, then increment i and then swap i and j . This seems to be working for all the datasets. I just want to know, does the order of swap and increment of i matters or not ? Am i missing something here ? Thank you once again for all the help.
is the code sample broken?
The code is correct, the explanation in the video is a bit wrong
@@diehawks Yeah, I thought I was the only one who thought this. I seriously find this quicksort thing so hard to grasp and I have found few internet explanations that allow me to sink in this algorithm.
You are awesome !!!!!!!!!!
thx
Hello. I have a question. Im 10:25 and i dont understand why the complexity in this case is 0(n^2) . It should not be n! ? Because there are n-1 steps , n-2 steps , n-3 ... 1 ?
Was this for worst case?
@@BackToBackSWE yes . But i continued to watch this and i understood.
Because there are n + (n-1)+...+1 and this is the gauss sum