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.
Duplicate Keys
Loading...
From the course by Princeton University
Algorithms, Part I
3801 оценки
From the lesson
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.
Meet the Instructors
Kevin WayneSenior Lecturer
Computer Science
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Now we're going to take a look at what happens when we have significant numbers
of duplicate keys which is not at all unusual in practical applications. So, in,
in fact, often, the purpose of a sort is to bring items with equal keys together
for like the example that I gave where we had cities and time. There's a lot of
detailed data and the time and maybe the whole goal of the sort is to group them by
cities so we can ship out the data for each city, to each city and there's plenty
of other examples like that in data processing where we find maybe remove
duplicates from a mailing list or all the job applicants that we get, we might want
to sort them by the college attendant. So the sort does huge files with huge numbers
of duplicate keys. So, a sort, it's worthwhile to take a careful look at what
the implication of that is. So again, typical characteristics we have a huge
file but small number of different key values. So let's look at our algorithms in
that situation. So Mergesort, it doesn't matter that much what the key values are
like and it's actually, we can show that Mergesort always uses between one-half, N
log N and N log N compares. Quicksort actually, they're up until the 1990s the
most widely used implementation took quadratic time. For files with large
numbers of equal keys and that was actually found by applications user and,
and that's the standard Quicksort that was in all the textbooks almost all the
textbooks if you did not stop the partitioning on equal keys it would run in
quadratic time. So we want to do better than this. So the mistake happens if we
put all the items equal to the partitioning item on one side which is a
natural way to implement it and the consequence is if you have all the keys
equal, then partitioning doesn't really do anything. You just peels off one key to do
file size n then you get a sub file size n - one and then n - two and so forth and
the result is a quadratic tim e algorithm. Our implementation, we stopped the
partitioning scans on items equal to the partitioning item and then in that case,
when all the keys are equal, it's going to divide it exactly in the middle. And then
in that case, when all the keys are equal, it's going to divide at exactly in the
middle. And then in that case you get an N log N compares. But actually when you
think about it, why don't we just put all the items equal to the partitioning item
in place. That's, that's really a desirable way to look at it and let's take
a look at that option. So the goal is so called three way partitioning. So what we
want to do is get the array into three parts so then now we have two pointers
into the middle. One that is the boundary between the keys that are less than the
partitioning element and those that are equal of the partitioning element. Another
one that's the boundary between the keys that are equal of partitioning elements
and the one that is greater. And then in the middle are all the equal keys and
that's what we'd like to arrange. Now until the 1990s, conventional wisdom among
people implementing system was, wasn't worth doing this. But, but actually it's a
problem that Edsger Dijkstra had proposed in the 70s as an example of, of
programming problem. He was really interested in analyzing correctness of
programs and showing that this how you could convince yourself that this program
was operating as expected. But in the 1990s we figured out that really this was
going to be an effective way to sort. And this was taking a look at the Qsort that a
user found was broken and, and now, this method is incorporated into some plenty of
system sorts. So let's take a look at how it works with the demo its more
complicated than standard Quicksort partitioning. A bit more complicated
because there's more to do. So now we have our i pointer which is right to the left
of stuff we haven't seen ye t and then, we have two other pointers that maintain,
maintain these boundaries everything to the right of gt is known to be greater
than partitioning element. Everything to the left of lt is known to be less and
between lt and i is known to be equal. And all the method does is maintain this in
variants so let's do an example or two and see how that works. So we increment i and
then figure out what to do. So, now it's less than the partitioning element. So,
what we want to do is increment lt's. So now we have one that's definitely less
than the partitioning element and lt is, is pointing at the partitioning element.
And so now in, increment both lt and i so that's the first case there. So now we
have a second item b. That's less than the partitioning element so exchange with lt
and increment them both. So, we're moving the smaller ones than the partitioning
element to the left of lt and keeping lt pointing on a partitioning element. Now,
what about when we get one that's greater than the partitioning elements? So, in
that case, we exchange greater the one over at the right with i and decrement gt.
So now, we have one over to the right that we know is greater than the partitioning
element. Notice that we didn't increment i because that element z that is over in the
right, really hasn't been compared to the partitioning element yet. But we did
decrement gt so we made progress. So now what happens here, now i is pointing to a
bigger one so we're going to exchange it with the one at gt and decrement gt again.
And again, y is bigger, so exchange it, decrement gt. Now we have the c, that one
smaller so that's the first case. So we'll move it to the left of lt and increment
both lt and i. W is a bigger one, let us to go over to the right. Now we have i
pointing to an element that's equal to the partitioning element. And what are we
supposed to do then? Well, to maintain the variant there we just need to increment i.
And again it 's pointing to one that's equal of partitioning element increment i.
And now one more time and now it's pointing to one that's greater so we
exchange that with gt and decrement gt and i is pointing to the one that was there
and that ones smaller. So we exchange it will lt and increment both i and lt and
now where the point, where the pointers have crossed i and gt across there's
nothing that we haven't examined yet. So, our partitioning is complete. Here's a
trace of Dijkstra 3-way partitioning for his problem which is when there's just
three different values in the file. Our problem we were treating partitioning,
equal of partitioning element as one value less than as another and greater than as
another. And so this, this trace illustrates how we always make some
progress and eventually we get the file sorted. The implementation is amazingly
simple. The whole partitioning process for three-way partitioning and the modern
programming language like Java simply maintains the invariances described in the
demo. If we find one that's less we exchange i and lt and increment them both.
If it's greater we exchange i and gt and decrement that. Otherwise, we increment i.
Could, could hardly be simpler. In fact, is simpler in many ways than these
standard implementation of Quicksort. In fact, there's an argument for just using
this implementation of Quicksort and forgetting about horse because it performs
so well in so many practical situations. Here's a visual trace of 3-way Quicksort
for situation with plenty of equal keys. And again, when there's a lot of equal
keys then there's going to be place where one of those is chosen, it's partitioning
element then a big chunk of the array gets handled just in a partitioning process.
Now, there's actually some deeper reasons why this method is important and one thing
to do is to realize that the lower bound that we talked about before depended on
the keys being distinct. So, worst case for lower bounds is when the keys are all
distinct. But if we have a situation where there are a lot of equal keys, that model
is wrong. It's not too difficult to get a similar lower bound for the model when we
know that there are some equal keys. So, for example this is a rather complicated
formula but not too bad but in a sense that if you know that the i-th key, it
occurs xi times you can write down a lower bound for the number of comparisons that
are going to be required in the worst case. And, what's interesting about three
way partitioning is that the number of compares that it uses is equal to this
lower bound within a constant factor. So that's entropy-optimal and what that means
is whatever the distribution of equal keys in there, this thing is going to use a
number of compares that's proportional to the best that you could possibly do. The
proof for this fact is quite beyond the scope of this course but it's still an
important fact. And the, the bottom line is that if you randomize the order and use
three-way partitioning then there's lot of applications where your sort routine is
going to be linear not N log N so it will be much more faster than Mergesort and you
know, the methods for really a broad class of applications. So, taking a look at
equal keys is carefully is something that can lead us to very efficient Quicksort
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
