Skip to main content
Loading Explore guides…
Quicksort Algorithm · Acedra
Home
Explore
Computer Science
Quicksort Algorithm
Sign in to save
Chat
If YouTube asks you to sign in, open the video on YouTube.
Watch on YouTube
Reload player
Transcript
13 segments
Copy
Hide video
0:00
[I] can show you an algorithm called Quicksort
0:04
[hopefully] this bit of paper here will be sufficient to do that okay, so again. We start with unsorted list
0:14
this time we Partition the list into two bits so rather than just fitting into two bits of equal size [we] take one element which we call the pivot. It doesn't really matter which one you pick I mean Actually, it does matter a little bit. I which I'll get into in a minute okay, so we pick one call the pivot We'll take the Rightmost one okay So we've got five so put that there [so]
0:33
Every element in this list that is less than or equal to five goes [in] this side and every element that's greater than it goes On this side so seven goes on the right eight goes on the right seven goes on the right Four goes on the left three goes on the left [10] goes on the right so then we do the same again for these two sub lists we've got so we take three as the pivot for this one and Four is greater than x or goes on the right?
0:57
so with this one we take take 10 as the pivot so everything less goes on the left so it's actually all the elements and
1:08
Then we keep breaking these down [so] we've got either one element or no elements in each list so we know they're sorted okay So we take seven as the pivot eight goes on the right and seven? Less or equal goes on the left so then we rejoin these lists back together so start at the bottom we Take the pivot everything on the [left] goes behind it everything on the right goes on top of it, okay?
1:30
So we've got the pivot here put four on top of it got 10 here everything [we] left goes behind it and then here we've got the pivot so these go on that's left and
1:42
These go on it's right Okay, so now we've got one sorted list Now you do have to be careful about what you choose ask the pivots usually what they'll do is You'll either pick the first element or the last element because it's just easier ideally you want to be able split the lessons about to even part so really want the pivot to be the Middle most number, but you don't know what that is at the start so in the average case It's the same as merge, Sort we've got end times
2:09
And in the best case it's still a login, but in the worst case well, let me show you okay? So let's say we've got a list that's already Sorted So I just take the cars without before if we always choose a pivot from the Rightmost element We've got ten so it ends the pivot so all the elements [left] on it. Go on the left. We've got all the elements [basically]
2:33
Okay, so then we pick eight as the next pivot all the elements go on its left when you pick seven as the next then all the rest go on the left and pick the next seven and what you see is we end up with cars all the Way down here, and then [we've] got to merge them back together
2:49
Okay, and actually that works out in the worst case As N squared so again, it's the square of the [input] size, so we've got the worst case bubble, Sort is still n. Squared and
3:01
The worst Cater Merge, Sort is it's still n. Log N
3:08
The highest card will definitely have been swapped all the way to the end So actually you don't need to check [that] one anymore. You can move that off and you [just] get these third-party cookies Hello the advertisers to figure out have you seen this advert before?
Here to help you learn
Sign in to keep a private conversation with your course tutor.
Ask me anything about the material…
Sign in to chat