Video 3-3: §3.2 Quicksort

0:00 Introduction to quicksort

0:02 in the next subsection i want to talk about quick sorts uh it's fair to say that um that's my favorite sorting algorithm i've worked a lot personally on researching quicksort um i may actually be the person with the most papers on quicksort and well i've worked a lot on this so i have to keep myself to keeping the presentation here short i have a lot more to say about this beautiful algorithm but in the interest of time and for your sanity i'll i'll not do it

0:41 i i asked you on slido what is the main principle behind quicksort and let's briefly switch there 20 people who have voted i'll give you a few more seconds to make up your mind

1:12 but i guess many will have seen this all right so there's a few don't knows um and we'll definitely have to change that and um a couple of uh votes for the other things but the vast majority has the right idea in mind um

1:36 i should say that this split elements around around the pivot element would be i think a more more appropriate way to phrase it okay uh thanks for voting and then we can continue so yes indeed uh the essence of quicksort is to take an element to compare this with the other elements and split them into the smaller i have to move move over here split them into the smaller and bigger elements and recursively sort these two

2:13 there's a bit of the you can you can do the details of this procedure in a better or worse way and i'll show you one of the better ways

2:22 Partitioning procedure

2:25 so again pictographically what quicksort does is called partitioning and uh yeah i'll show it like this so you have a and completely unsorted list there it can be can go arbitrarily up and down after partitioning there is a pivot point here where if you're on the left you're below the dashed line and if you're on the right you're above the bash the dashed line that's the idea of partitioning how can you do this so here's your unsorted list arbitrarily up and down you nominate one element as the pivot element and in this case i just took the first one no no magic behind this

3:16 and then we started a process where we we have to uh pointers that scan the array one from the left and one from the right and we'll compare elements uh with this pivot so this is indicated with these uh arrows below the elements that's where we currently look at this first element is smaller than the pivot and it's on the left side remember our goal is to produce something like this so for the moment this element is where it's supposed to be it's on the left side of well wherever the boundary will be but that's what that one's good so we can keep it where it is and we move on to the next element this is a bigger one it's bigger than the pivot so it has to go to the right side we don't know where the right side is at the moment but that's now the key trick here we just remember that it's on the wrong side and now we start a process from the other end and look what elements we find there the first one is big which means it's on the right side and so we just leave it where it is but the next the next element is smaller than the pivot so these two now we have a pair of elements that are both

4:23 in the wrong order uh why don't we just swap the two and with one swap we get both elements on the right side on the side that they belong that's what makes this partitioning method efficient you get two things done in one step okay let's uh look how this continues um you find some more and then one last pair that's out of order and now this at this step uh you notice that the these two pointers that start at opposite ends they have crossed they have reached a common point and that's your signal that you're actually done [Music] now the only thing that remains is to put your pivot element in the middle and then you have exactly this this picture from here there's the the dashed line right it's just given by the pivot element itself and uh we return this position

5:22 that's another important part of partitioning because um i mean here this is almost in the middle but we don't have a guarantee it could be slightly more to the left slightly more to the right that's not something we know up front

5:44 okay a few remarks we don't need extra space this is all inside the original array we don't we only swap elements around we don't have to copy them into a buffer space like in merge sort we visit every element exactly once uh we kept the pointer on on one of the left side occasionally and had to wait till some partner was found on the right side but that point is still it just stays there so we count that as as one visit which makes sense in terms of memory accesses again i have more to say on this but

6:23 not here not now uh ask me offline if you're interested uh and the last point what i already said we return as the return value from the partitioning procedure we return the position of the pivot at the end good with that preparation we can

6:36 Implementation details

6:39 give the the detailed code for quick sort now it's not ideal this is uh the partitioning procedure that describes precisely what i've just shown you uh in this example now um i'm not claiming there's any rocket science going on but it turns out that this partitioning procedure is very easy to break and get wrong so if you ever have to implement this yourself and cannot use a library implementation consider using precisely this code because that's the one that the quick sort expert recommends and that's not just me it's also robert cedric is the the other quickstart expert and his work done on this code as well that's the one that avoids all the known pitfalls and just works as given apart from that i don't want to come and comment more on the code it's doing exactly what i showed in the example there's a pointer i starting on the left there's a pointer j starting on the right and then they move towards each other uh one step at a time as long as you're smaller than than this pivot element which is always in in the first position here

8:06 one comment here is you can pass the partitioning method a position that you want it to use for the pivot element and let me just swap that to the first position um yeah and this picture below that i'm hiding here is uh the invariant that uh holds during the execution there's the part on the left of i that's small the part on the right of g of j that's big the part between them is unknown as of yet and the pivot is in the in the first position um there was a question on slido um

8:49 this is a an interesting remark let me flag the question so it's it's true that you can very easily write um very short code in functional programming languages for methods like quick sort um i think the same is true maybe not three lines oh you changed it to four lines

9:14 i think the same is true for merge sort pretty much i don't think it necessarily means that it's faster in functional programming languages because to give you this convenience to be able to specify it in just a few lines functional programming languages have a larger body of things going on below and whether or not that's faster depends on a lot of things in particular for sorting which is generally an easy problem it's fast in almost no matter what you do almost

9:49 a lot of small things matter and one of these things is how you access memory and functional programming is not always the smartest way to control that they are sometimes [Music] a bit wasteful on on the low level side of things but i'm not saying anything against haskell they also often have very clever optimizations that they can do

10:14 i think the true answer is you have to do a running time experiment and find out so you're welcome to to do this and and report back on the results um i'm always interested in uh what comes out of these things

10:30 um so if you do implement it in a sequential in a procedural language this is the partitioning code that you should use um the haskell based representation is is likely small slower than this one like for merge sort we can use the partitioning procedure to write a recursive sorting method and that's then quicksort so again quicksort is given a range that we're sorting in this array and initially it's just one through n the entire thing if the range that we're given is actually empty or just a single element we don't do anything otherwise we choose a pivot and some comments on that in a second after we've done that we call the partitioning function and then we recurse on the left and right side right this is just the range to the left of the pivot position and to the right

10:45 Pivot selection strategies

11:28 okay the choice of the pivot turns out to be very important um we'll come back to that if you take any fixed position like the first one uh that's a bad idea because you can get worst case inputs very easily and they might not be infrequent

11:50 a random position is much much better than that it's a very sensible choice what practitioners usually prefer is use something that makes a worst case very unlikely but still avoid randomness for some reason so for example you can take three elements sort them and take the middle of those three that at least guarantees you that it's not the smallest and not the largest in the array that you get as pivot but something closer to the median um ideally you want to choose three random elements and do this then you get the the most reliable results now i think this is an easy question for most of you but i want to ask it anyways uh what's the worst case running time of quicksort so this is uh important of course

12:51 uh remember for merge swords it was it was true that the average case and the worst case is essentially the same exactly the same in our cost measure of element visits

13:07 for quicksort uh as you may know this is this is not the case and um that's that's definitely an important piece of knowledge that you should have um let's see uh if i can jump over the result slides and um

13:45 i'm trying to get at least 25 or so before i close it we've had up to 37 votes in today's session so there must be some more people around okay there you go 25 i said i'll show the results when we're at 25. uh so there's a big peak for quadratic and that's the right answer um i tried to put a lot of different things in just to make it a little confusing for you or to show what else would be possible but um yeah quadratic is the right answer and we'll uh we'll see in a second why um oopsies that's definitely not correct have to fix this lights uh that would be nice but not true um how comes that we have this worst case uh to to understand that intuitively i think the following connection between quicksort and binary search trees that we've just covered yesterday and today more and earlier today a connection between those two is very insightful so um let's let's have a look at that um that might be one of the things that you haven't seen in in previous classes so uh everybody wake up again let's see how a simple quick sort would work when sorting this array of numbers we would pick a pivot let's say we take

14:43 Recursion trees and analysis

15:22 the first one here for simplicity then we partition the lists we just keep all the smaller elements on the left and we keep we put the big elements to the right and uh well i can put the pivot then between those two parts that's how one partitioning step looked like and i keep these boxes around the ranges that we still have to sort so that this becomes a bit more easier to see we do another round of partitioning pick a pivot partition into two parts put the pivot in between you know how this goes you do the same thing for that one and well you keep keep going right and ultimately uh every single element is just chosen as a pivot of itself and there's nothing really to partition but let's add that to the picture um what i added here now is the recursive call tree there was one recursive call where 7 was chosen as pivot and that split that was actually the call when this was the array and it splits the list into two parts this small segment on the right and this bigger segment on the left and that means the recursive call where 7 was the pivot has two child recursive calls and two child trees the one to the right with uh well this

16:43 one where the pivot was nine and on the left where the pivot was four so you just connect recursive calls with this parent child relationship and you get this tree okay so far so good um let's take the same list these are the same numbers in the same order right and insert them into a binary search tree a standard one not the balanced one just one like i've shown you insert yesterday we start with the seven that's the the first element that becomes the root and it stays there then we we insert the four four smaller than seven so it has to be the left child of seven next is the two it's smaller than seven so we walk down here four two is smaller than four so we walk down here that we find a null pointer and insert it you remember how this goes so let me speed up a bit with the other elements and uh if you just do this insert the one after each other you notice you get this binary search tree and that looks very much like this recursive uh by this recursion tree on the left and that's no coincidence this is what always happens the recursion tree in quick sort is exactly the same as this binary search tree that you get

18:02 from inserting if you if you pick pivots differently than this nice simple version of quicksort you get the result looks slightly different but it's still essentially true the same same result is still essentially true so we can treat recursion trees of quicksort like binary search trees built from just this this sequence of numbers and the connection is is very one-to-one um if you look at the comparisons that you do in quicksort these are exactly the comparisons that you do to build this binary search tree now let's maybe illustrate this this point um one more time because that's um it's it's kind of clear but uh maybe not so obvious at first um if you see this the first time um let's take um the number number two how does two find its position in the final sorted list in quicksort in the first round two is compared to seven and is found smaller the second round two is compared to four and is found smaller and then two is the pivot so it's stuck there so two participated in two comparisons it was compared with seven and it was compared with 4. now let's look how you inserted 2 into this binary search tree

19:33 you compared with 7 at the time and found it was smaller you compared with 4 at the time and found it was smaller and then you inserted it here where because this part was empty at the time remember so you do exactly the same comparisons and you can even look at the final tree and look at the number of comparisons you need to search the two if i search for the two i do the same step i traverse this the only thing at the end i compare with this element and you can you can argue you do an extra comparison to decide that you have to stop here but this is this is really a key observation here so you can analyze and understand uh this this complicated object quicksort which modifies the array over time you can understand it using a static object namely a fixed binary search tree that's just built from from randomly inserting the elements and well we've already talked about how search trees look like so you've seen this picture hand-drawn last time a binary search tree can look like this and then it has height n and that also translates into a very bad case for quick sort you can you can work this out effectively it's at each element you have to pay the size

20:55 of the subtree because that's how many comparisons this one participates in and if you sum this up you get a quadratic number and that's uh your worst case for quick sort as well

21:12 for binary search trees we were stuck at this point with either going to a balanced binary search tree or saying hopefully the input is not too bad hopefully the user is nice and does not insert elements in sorted order now here we have an additional option we can explicitly randomize by choosing a random pivot in each step we explicitly force to have the good average case instead of whatever the the terrible worst case would have been remember that um the elements in the in this tree they're chosen as the pivot in this step so um we can by randomly choosing the pivot we can force quicksort to always have the good average case in expectation and only with a very small probability we get something different and we can do this by by just randomly shuffling the input before we sort uh that might sound a bit uh absurd or or crazy why if you try to bring order into a file the best thing to do is to first completely destroy any existing order and randomly shuffle it but yes this is sensible this is the right thing to do for quicksort uh that's exactly how you um get the the most reliable results in quicksort the most reliable performance

22:39 Summary and performance

22:42 all right i have one more slide with some results on this but without going into much detail on this you can work out a similar recurrence for the number of element visits for quicksort but i will spare you the details because the calculations are a bit longer and i think um this is a bit off the point uh to do that in more detail but you can do this and then you find the the result is is this which um well this is this is a constant that you can approximate it's uh 2 is is 1.39

23:16 and remember we had for merge sort a similar result but it was 2 n log base 2 of n so in a sense uh quick sort brought this factor 2 down to a factor of 1.39 it's only a an improvement by a constant factor but it's a fairly significant one and this is also what people find in practice if you implement quicksort properly um with the randomization and uh with taking care of of the the low-level details it's usually a good deal faster than merge sort easily 50 faster and that's that's roughly reflected in these numbers as well you can do much more mathematical analysis on quick sort for example you can prove that it's very unlikely to be much worse than this expected case so this is um the typical performance but if you randomize you sometimes get worse performance but you can prove some things like this uh the probability that cost is uh well roughly whatever it is seven times more than the expected cost is is um going to zero if you make the input smaller like like this uh almost like um like a cubic frame or

24:40 at least it it goes it goes very quick quickly to zero let's uh leave it at that so you can you can prove that the costs are concentrated around their mean you usually get this not just an expectation but with very high probability and the intuition behind this is to not get something good you have to be constantly unlucky by repeatedly choosing a really bad pivot and that's unlikely to happen

25:12 okay so so much for the analysis parts this is the last slide is is basically just for your interest to wrap up the discussion of quicksort it's the appropriately for its name

25:29 um it's the fastest general purpose sorting method in practice and all library all programming libraries i know of have a quick sort implementation there's a particularly interesting story behind the implementation for the java runtime library um a story that i told in the welcome week talk in the last fall if you're interested to see this i can send you a link but you don't need to know this for our module it has this the same performance like merge sort in the average case or as i just commented lengthily in with with high probability and all that if you randomize uh and another good thing that merge sort couldn't do is it works in place it doesn't need really any extra space apart from the recursion call stack but that's very very little compared to the large buffer area that merge sort needed like merge sword memory accesses are sequential so you don't get into trouble with caches what's bad about quick sort is this annoyingly slow worst case but for practical purposes it's largely irrelevant if you do the proper randomization it's probably more likely that a sun flare destroys your computer than that quicksort really gives you bad performance it is not a stable sorting method that is um the big downside also for practical applications

26:58 for some applications where this is relevant uh it's it's not clear how to fix this and keep the other good properties whereas merge sort was stable so the usual the usual choice in practice is if you need a stable sorting method go for merge sort if not take quicksort because it's faster and this is another fundamental open problem in uh in sorting find a simple algorithm that is fast in practice sorts stably and is in place works in place if you leave out any of the three there are solutions known but combining all three no one has really convincingly done so far