0:05

It was named as one of the most important algorithms of the twentieth century and

Â it's widely used for system sorts and many other applications.

Â Last lecture, we looked at Mergesort, another classic sorting algorithm, that's

Â used in many systems, and today we are looking at Quicksort which is used in many

Â others. You can even get a Quicksort t-shirt

Â nowadays. So what is the Quicksort method?

Â It's also a recursive method, but the basic idea behind Quicksort is that it

Â does the recursion after it does the work, whereas Mergesort did it before it did the

Â work. So, the idea is first randomly shuffle the

Â array. That's an important step that we'll talk

Â about later, and then partition the array, so that's to divide it so that for sum

Â value j the entry a of j is in place in the array.

Â There's no larger entry to the left of j and no smaller entry to the right of j.

Â Once we have the array partitioned in that way, shown here in the middle.

Â Right here, we have K in its position. And we have everybody to the left.

Â There's nobody greater than K. And everybody to the right, there's nobody

Â less. Once we have it arranged in that way, then

Â we recursively sort the two parts. Sort the left part, sort the right part.

Â And then after those two things are done, the whole thing is sorted.

Â This method was invented in 1961 by Tony Hore, who won the Turing Award in 1980 for

Â this and other work. So let's look at a demo of how Quicksort

Â partitioning works. The idea is to arbitrarily choose the

Â first element to be the partitioning element.

Â Since we shuffled the array, that's our random element from the array.

Â And then we're going to maintain an I pointer that moves from left to right, and

Â a J pointer that moves from right to left. Let's look how it works in the demo.

Â So we start again by picking K as the partitioning element.

Â And then our method is to move the I pointer from left to right.

Â As long as what we have is less than the partitioning element.

Â And move the j pointer from right to left as long as it points to an item that's

Â greater than the partitioning element. So, in this example the i pointer stops

Â right away because it's pointing to an r which is bigger than the partitioning

Â element. The j pointer decrements until it gets to

Â the c which it stops there which is less than the partitioning element.

Â And so now what's going to happen is those two elements are out of place.

Â The partitioning elements in between them and they're in the wrong order.

Â So what we want to do is exchange those. And then move on.

Â Now we increment I, as long as it's pointing to an element that's less than

Â the partitioning element. Stop here at t cuz that's bigger.

Â And now we decrement j, as long as it's pointing to something that's bigger than

Â the partitioning element. Stop her at I because that's less.

Â Again, t and I are in the wrong places. If we exchange them, we'll maintain the

Â invariant that everything to the left of I is less than the partitioning element, or

Â nothing to the left of I is greater than the partitioning element, and nothing to

Â the right of j is less than the partitioning element.

Â So exchange increment I as long as it's less.

Â Stop at l increment j decrement j as long as it's greater.

Â Stop at e those two elements are out of position so exchange them.

Â Now increment i, stop at the l which is greater than k decrement j stop at the e

Â which is less than k and now at this point the partitioning process is complete,

Â coomplete cause the pointers have crossed and we have looked at everything in the

Â array. In fact.

Â J points to the, rightmost element in the left subfiles, everything that's not

Â greater than K. So we can just exchange J with our

Â partitioning element. And now we've achieved the goal of

Â partitioning the array. So that A of J is in its position.

Â Nobody to the left is greater. Nobody to the right is less.

Â Now, the code for partitioning is straight forward to implement.

Â Down below. Shows the state of the array before

Â partitioning. During and after partitioning.

Â So in the end, the J pointer is pointing to the partitioning element V, which was

Â in position V in the first place. In the, all during the partitioning

Â process, the code is maintaining this invariant.

Â Where everything to the left of I is less than or equal to V.

Â Everything to the right of J is greater than or equal to V.

Â And we haven't looked at things in between.

Â So, finding, incrementing I, as long as it's less is a simple while loop.

Â And then we put a test to make sure we don't run off the right end of the array.

Â And decrementing J. As long as it's pointing to a bigger

Â element that's similarly just a wide loop we put in to test to make sure we don't

Â run off the left end of the array. Then there's a test to see if the pointers

Â cross. Swap the elements of I and j.

Â When we get to the pointers cross we break out of the loop and exchange the

Â partitioning element into position. So that's a quick implementation of the

Â Quicksort partitioning method. Now, Quicksort itself then is going to be

Â a recursive program that uses that partitioning method.

Â First thing we do is the public sort method that takes the array of comparable

Â items as its argument. It's gonna to do a shuffle.

Â And that shuffle is needed to make sure that we can guarantee that the performance

Â is gonna be good. And then it calls the recursive method

Â that takes as arguments the limits of the subarray that's gonna be sorted.

Â So then partitioning. Simply does the partitioning.

Â Tells us where, which element is in position, and then recursively sorts the

Â last part that's loaded, J -one. And then the right part, that's J + one to

Â high. That's a complete implementation of

Â Quicksort. Again, as with Mergesort, studying a

Â recursive trace is instructive. And this one is kind of upside down as

Â compared to Mergesort. The first line shows the partitioning

Â where k is put into position. Then the method calls the sort for the

Â left subfile first, and then that's gonna be partitioned on this e, and so forth.

Â And eventually we get down to small subfiles, actually our code doesn't do

Â anything at all for subarrays of size one, so we just leave those in gray, and then

Â it does the right subfile, and so forth. Again, studying this, a, a trace like

Â this, gives a, a good feeling for exactly what's going on in the recursive program.

Â Let's look at an animation of Quicksort in operation.

Â There's the partition. Now it's working on the left.

Â Now it's partitioning the right. Now it's working on the left part of the

Â right. Now it's partitioning what's left.

Â Doing the left part of that. And working from left to right, by

Â dividing each sub-array in half as it goes.

Â So let's look. Consider some of the details in

Â implementation of partitioning with quick sort.

Â So first thing is the partition is in place.

Â You could use an extra array and the partitioning code would be a little bit

Â easier. But one of the big advantages of Quicksort

Â over Mergesort is that it doesn't take any extra space.

Â It gets the sort done in place. Now you have to be a little bit careful

Â with terminating the loop. When we give you working code it's not

Â hard to see why it works. And you might go trough the exercise of

Â trying to implement Quicksort without looking at our code, and you'll find that

Â testing when the pointers cross can be a little bit tricky, particulary in the

Â presence of duplicate keys. Also staying in bounds.

Â And I, actually, in our implementation the test of the J pointer running off the left

Â end is redundant. Why is it redundant?

Â Well, the partitioning element is sitting there and it'll stop when it hits the

Â partitioning element. But the other test is not in our

Â implementation. And the key thing, one key thing is that

Â the way that these implementations work. If the in-, the file is, the array is

Â randomly ordered, then the two sub-arrays after partitioning will also be randomly

Â ordered. Actually, some implementations of Quick

Â Sort out in the wild don't have this property, and they suffer a little bit in

Â performance. That random shuffle at the beginning is

Â important and needed for guaranteeing performance.

Â And the other thing I have referred to but not talked about in detail is the presence

Â of equal keys. You might think it would be better to

Â handle equal keys in some special way. We'll talk about that in a second.

Â But this general purpose implementation stops the pointers on keys equal to the

Â partitioning items key and we'll take a look at why that's important in a minute.

Â So now let's look at the running time estimates about why we care about

Â Quicksort vs Mergesort. This is extending the table we looked at

Â last time, and you can see over in the right column here, Quicksort is quite a

Â bit faster than Mergesort. And again, a good algorithm is much better

Â than having a super computer. Even on your PC you can sort huge array of

Â a million items in less then a second and a million items in only a few minutes.

Â So again this time, sort of timing is why Quicksort is so widely used.

Â Cuz it's simply just faster than Mergesort.

Â Well in the best case Quick Sort will divide everything exactly in half.

Â And that makes it kind of like Merge Sort. It's about analog in.

Â And in the worst case if the random shuffle winds up putting the items exactly

Â in order, then partitioning doesn't, doesn't really do anything except find the

Â smallest, peel off the smallest item. Kind of discover that everything to the

Â right is greater. That's a bad case.

Â But if we shuffled randomly, it's extremely unlikely to happen.

Â Most interesting thing about the study of Quicksort is the average case analysis.

Â This is a somewhat detailed mathematical derivation, but it is worthwhile going

Â through the steps, to really get a feeling for why it is that, Quicksort is quick.

Â So what we do is, as we did for Merge Sort, is write down a mathematical

Â recurrence relation that corresponds to what the program does.

Â In the case of Quick Sort, the number of comparisons taken to sort N items is N+1

Â for the partitioning. Plus what happens next depends on what the

Â partitioning element was. If the partitioning element is K.

Â Any particular value happens with probability one over n, and if it's k,

Â then the left subfile has k - one items in it, and the right subfile has n - k items

Â in it. So, for every value of k, if you add those

Â up the probability that the partitioning element is k, plus the cost for the two

Â subfiles, we get this equation. This looks like a fairly daunting

Â equation, but actually it's not too difficult to solve.

Â First thing we do is just multiply by N and collect terms.

Â So NCN N times N + one. And then these terms, every size appears

Â twice. So it's twice the sum of from C0 to CN -

Â one. It's a simpler equation already.

Â Now what we can do is get rid of that sum by subtracting the same equation for N

Â minus one. So NCN - N - one, CN - one then the N, N +

Â one - N - one N is just 2N. And then the sum collapses just leaving

Â the last term. This sum, minus the same sum for N - one,

Â just leaves the 2CN - one. Now that's looking like a much simpler

Â equation. Rearrange the terms, so we get n+1 cn-1

Â and then divided by n, n+1. That's a kind of a magic step, but we will

Â see that it makes possible to solve the equation easily.

Â Because that equation, with C over N plus one equals CN minus one over N, is an

Â equation that telescopes the first term at the right.

Â It's the same as the term on the left. So we can apply the same equation so its

Â two over n + one. We apply for n - one we get one less here

Â and we can throw out a lot two over n. And continue that way throwing out two

Â over decreasing numbers all the way down until we get down to two elements, c1

Â which is zero. Substitute the previous equation

Â telescope. And then that gives us an easy sum that we

Â can approximate by an integral. It's one over X from three to N+1.

Â And that's a pretty close approximation, in this case.

Â And that approximation gives us, it's about two M+1 natural log N comparisons

Â for Quicksort. About 1.39 N log N.

Â That's the average number of comparisons taken by Quicksort, and actually they for

Â a random permutation of the elements which is what we do with the shuffle.

Â They the expected number of comparisons is concentrated around this value.

Â It's very likely to be very near this value is then as large.

Â So the worst case quick sort is quadratic. So complexity's going to tell us that it's

Â a quadratic algorithm if that's what its worst case is.

Â But with random, the random shuffle it's more likely that this lecture will end,

Â because of a lightning strike. Or your computer will be struck by a

Â lightning bolt. So we can discount that.

Â The average case, which is extremely likely for any practical application, is

Â going to be about 1.39 n log n. So that's more compares than Mergesort

Â uses. But Quicksort is much faster, because it

Â doesn't do much corresponding to each compare.

Â It just does the compare and increment a pointer.

Â Whereas, Mergesort has to move the items into and out of the auxiliary array, which

Â is more expensive. So the random shuffle is a key for good

Â performance in Quicksort. It gives us the guarantee that the worst

Â case is not gonna happen. And also, it allows us to develop a math

Â model that we can go ahead and validate with experimentation.

Â You run Quick Sort and you count compares. If you did the random shuffle, it'll be

Â about 1.39 n log n compares. And its running time will be proportional

Â to n log n, and it'll be a fast sort. And that's what people do, and that's why

Â people use it. Now there are some things that you have to

Â watch out for with Quicksort because the implementation is a bit fragile and it's

Â easy to make mistakes. And you'll find textbook implementations

Â or implementations out on the web that wind up running in quadratic time in

Â certain situations. You have to be a little bit careful of

Â that and even if everything is randomized if there's lots of duplicates and the

Â implementation is not done quite right the quick sort might take quadratic time.

Â So, let's summarize the properties of Quicksort.

Â It's in place. It doesn't use any extra space.

Â The depth of recursion. So tha, that's.

Â Again, dependent on the random shuffling, is going to be logarithmic.

Â You can, limit the depth of recursion by always doing the smaller sub-array before

Â the larger sub-array. But that's not really necessary nowadays,

Â as long as you've done the, random shuffle Oh, and by the way, Quicksort is not

Â stable cuz partitioning does one of those long range exchanges that might put a, a

Â key with equal value over a key another key with the same value.

Â So it's a little more work to make Quicksort stable, maybe using extra space.

Â Un, so what about in actually in practice? This is our fastest sorting algorithm, and

Â there's a few ways to make it even faster. And these, we looked at some similar

Â things with for the Word, Mergesort. And it's definitely worthwhile taking

Â implementing for a Quicksort. First thing is small sub-arrays.

Â Even Quicksort has more overhead than you want for a tiny array, like one of size

Â two or three or four. So can implement it to cut off to

Â insertion sort for small arrays. And the exact number they use is not too,

Â critical. Okay.

Â Anywhere between ten and twenty will improve the running time by maybe twenty%.

Â Also you could just not do anything for small arrays, and then do the insertion

Â sorting in one pass at the end. So, that's a first improvement.

Â A second improvement is to, try to estimate the partitioning element to be

Â near the middle. Rather than just arbitrarily using the

Â first element. Which on average will be at the middle.

Â So one thing that we can do is sample the items, and then take a median of the

Â sample. And that's actually not worth the cost for

Â enlarged samples, not usually. But for three it's worthwhile.

Â Slightly reduces the number of compares. Increases the number of exchanges

Â paradoxically, cuz more exchanges are required when the partition is right in

Â the middle. So that'll also improve the running time

Â by maybe ten%. So this is a summary of the optimized

Â Quicksort with cut off the small subfiles in median-of-three partitioning.

Â So partition usually happens pretty close to the middle when you do that sample

Â median-of-three and then small subfiles can just be left unsorted to be picked up

Â with insertion sort right at the end. So this gives a feeling for the.

Â Number of items that have to be touched during quick sort.

Â And kind of an explanation for how it gets the sort done so quickly.

Â That's a summary of Quicksort, our best sorting algorithm that we've seen to date.

Â