Quicksort

Loading...

En provenance du cours de Princeton University

Algorithms, Part I

4240 notes

Princeton University

Algorithms, Part I

4240 notes

This course covers the essential information that every serious programmer needs to know about algorithms and data structures, with emphasis on applications and scientific performance analysis of Java implementations. Part I covers elementary data structures, sorting, and searching algorithms. Part II focuses on graph- and string-processing algorithms. All the features of this course are available for free. It does not offer a certificate upon completion.

À partir de la leçon

Quicksort

We introduce and implement the randomized quicksort algorithm and analyze its performance. We also consider randomized quickselect, a quicksort variant which finds the kth smallest item in linear time. Finally, we consider 3-way quicksort, a variant of quicksort that works especially well in the presence of duplicate keys.

Duplicate Keys11:25

System Sorts11:50

Rencontrer les enseignants

Kevin Wayne
Senior Lecturer
Computer Science
Robert Sedgewick
William O. Baker *39 Professor of Computer Science
Computer Science

Welcome back. Today we're going to look at Quicksort.

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.

Explorer notre catalogue

Rejoignez-nous gratuitement et obtenez des recommendations, des mises à jour et des offres personnalisées.

Coursera propose un accès universel à la meilleure formation au monde, en partenariat avec des universités et des organisations du plus haut niveau, pour proposer des cours en ligne.

© 2018 Coursera Inc. Tous droits réservés.

Télécharger dans l'App Store

Disponible sur Google Play