Video 3-2: §3.2 Quicksort

0:02 the second Big Al sorting algorithm we'll discuss is quick sort in some way it's related to merge sword and has complementary um benefits and disadvantages so it's it's good to have both of these around uh again before we start let's do a a quick check of what you

0:30 know you see the patterns so um it's the same type of ansers same same set of answers from okay let's slowly move on um and okay so there's a majority vote which is which is correct um but there's a few more people not so well familiar with quick so maybe this is a good excuse to do uh this part a little slower um I I'll come back to it so similar to merge sord um we have one key step that we do and then we recurse to make that into a sorting algorithm for merge sort that was merging and for quick sort it's partitioning and again um a pictorial representation of this could be like this that squiggly line is supposed to mean there's no specific order in this array at this point so uh uh it looks smooth but it can jump around widely and after partitioning there's a pivot point so uh this point here where from that point to the left everything is below the value at this pivot point and from there to the right everything is above that Pivot Point right so the important bit is nothing in here and nothing in here that's what partitioning means in the context of of quick sort and let's see um how this is done

2:40 in a fast way uh on an array um it might not be exactly the version you've seen if you have seen quick sort before but this is quote the the right way to do it it has the stood the test of time and came out as the best option first of all we need a pivot element so we start by randomly choosing the per the the value that will eventually be this dividing line and that's going to be a tricky uh tricky choice but for now we'll just pick the first element out of better ideas and for the remaining elements we have to decide whether they are smaller or bigger than this element p and move them around accordingly and we start with um one pointer on this side so if uh that element here is smaller than the pivot that's fine so it's smaller that means we'll leave it where it is for now it's on the left so small should go on the left let we take the next one this is larger than the pivot so that means it has to end up in the right half of the array eventually so at this point we don't like it where it is but we uh wait before we do anything with it instead we

3:54 now start with a pointer on the other end of the array and do the same game but now this is a big element and it's on the right so that's what we like and we leave it where it is whereas if we find um an element that is small on but on the right that's again something we don't like and now we're in the fortunate situation we have two elements that are both in the wrong side ha let's just exchange them and that's what you do and then both of them are repaired at the same time and this kind of uh double progress that you make for one swap is what gives this method um usually an advantage over alternative ideas how you can do this

4:38 partitioning right then the next uh step is just continuing the same way so you take the next pointer that's a small one it can stay where it is you continue another small one stays where it is next one is large so we have to move from the other side so we start at the other end that's a large one can stay where it is that's a small one so we have again two ones that are wrong or Ed swap them then they're both happy and at this point you know that you're done when these two pointers that move towards each other have hit the same point there's one last thing that you have to do to get this picture which is swap the pivot in place of the last element of the first run now we have this this nice situation right there's this line and this line nothing in here and nothing stopping in here okay

5:36 a few remarks we did not need extra space all we needed was swapping elements around in the array that we've that we that we're given in in a vague sense at least we visit every element only once either from the left or from the right either from the left or from the right but we only touch it uh with one of the two pointers and what we can do for free this will become handy later is return the position where the pivot is at the end because it's it's lovely to be able to partition the array in some way but because we can't always guarantee where the dividing line is it's useful to know where it ended up being so we can return that from partitioning uh I put detail code for for the partitioning procedure on the slide in this case because unlike for merging this code is is uh surprisingly tricky to get right and has caused major performance buck in the history of quick sword so it's uh quick sword is a bit Infamous for being tricky to implement correctly it's not to say that it's an unsolvable task um but if you ever if you ever have to implement your own quick sword I highly recommend you to take an existing partitioning method um

6:50 and this is one of the one of the ones that is fairly uh robust against all sorts of performance issues I can talk more about this offline if you're curious that's it's an interest of mine and I worked on this but H it's not relevant for this uh module I just wanted to give you the definitive code in case you ever need it what's left is turning this into a sorting algorithm and now again we have something that does part of it it makes the array slightly more sorted but it doesn't do the entire job but what we can do is first do the partition so that we uh get into this situation where everything here is below blah blah blah everything here is above the key inform the key trick of partitioning is I can sort this and I can sort this part independently it will never happen that one element that's currently over here has to move to the left or vice versa because they're partitioned uh all the elements on this side are smaller than the pivot so in sorted order they have to be left of that pivot in code that looks like this so um let me just briefly go through it again it's a recursive procedure so we have

8:05 some range and the initial call would start with zero and N then um we stop if the array that we're looking at has only a single element then there's nothing to do let me just return otherwise we need a way to choose the pivot and I left it um generic here there's some function that chooses some pivot from this range A Simple Choice could be just pick the first element like in the example and that's an option but uh I'll comment on it in a second but there's some way to choose the pivot and uh get its position in the array and then we call partition where we we tell the method oh please use um this element as your partitioning element otherwise it's as in the example and what comes back is this position J where we have the dividing line between the two parts and then we can sort the left and right parts

9:21 independently and that's all so in quick sort all the work is done before the recursion in merge sword all the work is done after the recursion returns okay uh it's also a recursive procedure um similar to merge sword um the choice of the pivot is is fairly important and needs needs some thought but I'll only do this very quickly here one easy option is take the first element or some other fixed position but that um means you're potentially vulnerable to a bad worst case that someone might even exploit by explicitly giving you an input that makes you perform um a long computation much much better is a random Choice then at least no one can give you a single input that will make you fail this is very similar to binary search trees and the discussion of how tall how high the random binary search tree is and indeed there is a deep connection that will come to uh what often is done in practice is something in between so for some reason um programming libraries shy away from using Randomness they prefer to have things deterministic so instead people use something uh that is at least not quite as risky you take three elements and take the middle one of those as a pivot that is likely to be

10:39 better than taking a fixed position and has has a few benefits but it's still is somewhat vulnerable but these are the options before I tell you more about the analysis let's see uh again what you know there

11:07 this is also a um a welcome starter question for exams one possible such question okay again way too many answers to fit them on the screen nicely okay uh let me show you there's various bars and uh majority got it right but it's a it's a bit of a trick one so definitely remember this one like if you take nothing else from this subsection that's the one the one piece of information to keep but I hope you take more because there's a lot more um Nuance to this so the right answer first of all is n squ much much worse than n log N I want to keep you um once in a while I want to say a few things outside of the formal context log n is way smaller than n and hence n log n is way faster than n^ S okay maybe that's obvious um just if you look at the terms ah what what's what's the big deal if you actually run things it's such a big deal okay before we come to why that is the n squ worst case I want to show you instead some connection to something we've already seen and then we can recycle knowledge that's cool right we don't have to work twice uh we just have to make the

13:02 connection so let me show you um the connection in the nice way where I'll cheat a bit in the partitioning method if you uh if you catch me cheating you can show um I can comment on it offline again so uh let's have a quick example of how quicksort sorts this list uh it picks a pivot and I'm I'm assuming here I pick the first element just to make the analogy nicer it goes through in general I'll take all the smaller elements in the left all the bigger ones in the right and then pivot goes in between I'll give away the cheating that happens this is not using our partitioning method where I showed you the code it's one that is a little nicer to analyze but the same arguments would hold true it's just less transparent okay so forgive me for that one uh but I think you'll like the rest now that's not done right we have to recurse on this part and then this part for sorting so we do that find another pivot and again split into the elements smaller the elements bigger and the pivot in the middle uh that's not what I wanted jumped all the way to the end it's a long deck of

14:41 good so we've been here then we partition this again pick a pivot this time the the there's no elements bigger but that's all right that happens if you keep doing like this you get this kind of uh well picture now um let me put these uh lines in just for fun of it that's basically the recursion call so we have one recursive call that splits the entire list and it is left with that pivot element and then has a left and a right recursive call so it does two more recursive calls so I'm I'm just drawing the recursion tree but I'm I'm putting as the element representing that recursive call the pivot okay good without much um explanation let's take these element elements and insert them into a binary search tree with our procedure from last time seven is inserted first so it becomes the root and stays the root then four comes it's inserted is going to the left four is inserted it's smaller than seven smaller than four so it's inserted at this spot okay you see how this goes and if not watch the videos from yesterday again uh so you keep going like this and insert them in in this binary search tree and you see the left and right picture is

15:54 the same right this is this is the same shape here as this it's the very same tree H isn't that somehow interesting is that uh is that specific example where this happens no this is always true if you build the recursion tree like this you will always get the binary search tree that you would have got if you take the lists that you're sorting and insert them in the binary search tree in fact quick sort and binary search trees are very intimately related they're almost the same thing just uh doing things at different times um if you even look at the exact comparisons that are done in quick sort quick sorting that list or inserting the elements in that order into a BST it's the same comparisons uh they just happen in different

16:48 order uh forget about this this part that's that's the part I was I was talking about this is not so important for us here so what this means is by and large to analyze quick sword we can analyze binary search trees and uh we've already talked about those I haven't shown you the analysis but uh I made the appropriate

17:14 claims so that also means the worst case for quick sort happens if the recursion tree looks like this or the binary search tree that you get looks like this um the comparisons you need to build this is you need one comparison no comparison for the first element one to get the two down down there two to get the three down there four to get the four down there five so you're summing up the first so and so many integers that's this sum that's the famous little gaus allegedly discovered that formula in in primary school and so on but it's quadratic and so that's very slow now the easy fix is doing randomization if we choose to Pivot at random that is exactly the same as if we were building a binary search tree with random insertions because the two are essentially mimicking each other the very same thing

18:16 happens and so if you do this or if you uh assume that the input is shuffled before you go so um I went over this quickly uh an easy way to simulate the same thing is to before you start sorting you just randomly permute your array you randomly Shuffle it then you can also enforce the average case for quick sort um and you can you can show that the exact number of comparisons you need is is roughly this um again this is a our friend from unit one the Tilda approximation so ASM totically equal uh and you can prove statements like this um if you want to know How likely is it that quick Sur uses not 1.39 nlogn but 10 nln or more comparisons for your sorting of an of a list then you can show that it's that probability goes down if the list grows like uh like this one over n cubed n n squ

19:24 yeah uh yeah so when I say random pivot that means whenever you do a partitioning step you choose to Pivot randomly from the range at every recursive step so that's why uh it might be faster to do it to do the shuffling at the beginning once and for all and then not worry about Randomness depends on details but if you want to pick the random pivot you have to do it in each step at least for this result to be literally true the intuition behind this again this is uh a lot of math behind this that I won't get into um the intuition is for quick search to go bad or for a binary search tree to be really tall you have to be not just lucky unlucky a few times but constantly like uh in in quicker you would have to have a pivot that's very close to the smallest so that you keep this long list in the next recursive call and then it happens again that you only split off a very small range and you have to keep going like this for a very long time and that's just very unlikely because each time you're picking something random but I'm telling you no no no you uh you actually got something at the extreme ends and that's

20:34 unlikely to happen the further you go down the less likely it becomes so to wrap up on the discussion of quicksort um this is not something that follows from what I've shown you but if you do experiments with implementations quicksort turns out as the fastest general purpose method it's usually a bit faster than than merge sword um at least on on random inputs when there's nothing to exploit um the average case is n log n that's just restating what we had here um in expectation if you randomize the input order or on average if all input orders are equally likely H it doesn't need extra space that's the Big Boon over merge sort apart from being slightly faster often it doesn't need this buffer array

21:48 uh yeah it's great to schedule that during luxures but what can you do it's the schedule test H so don't worry the Bell still works we're uh safe so a quick sword doesn't need extra space that's a big Advantage um like merge sword the memory access is sequential in this sense that you walk over the array um without jumping around so that's the same um unfortunately has this worst case that we can't really discuss a way it's very unlikely but it's a possibility so sometimes that's a problem the other downside is it's not stable and it can't easily be made stable if you keep in place again as a theoretical puzzle you can make it stable and in place uh but then it's slow so it's uh it's not really something to go for uh the typical implementations of quick sword are not stable and I would even yeah put it as an open problem in a way that's as also interesting nobody really knows a simple algorithm that is explainable on few slides like this that's fast in practice and is stable and in place at the same time it seems these two things just uh are hard to