next we're gonna talk about 3-way radix quicksort which is that algorithm that
combines the benefits of quicksort and MSD radix sort.
This algorithm actually came to me into development during the development of this
course. As it turns out, radix sorting, while it
was really well known to everyone in the 60's and70's.
It was kind of lost sight of for a while in the'80's as people moved to a higher
level of programming languages. And it wasn't so easy or effecient to get
characters out of keys. You had to either work with numbers.
You had to use abstractions like compared to.
And radix sort got kind of lost for a while.
But then string processing became more and more important as.
Computers became bigger and faster and so we needed to talk about how to sort
strings and this algorithm is a really simple algorithm that comes out when you
start to address that problem. So, the idea is that what we're gonna do
is use 3-way partitioning for quicksort. But just by character.
So since there's a, we're gonna do one character at a time, there's gonna be a
lot of equal keys for that character. And the idea is that when you do have
equal keys, you'll pull'em together with those leading characters, and then you
could recursively sort the subarrays, but you can do the normal quicksort thing for
those. So for this example, when we partition,
first partitioning item, we're going to use it's first character, and we're going
to divide up into less than that. Equal to that and greater than that.
And then we re-curse three times, one for the greater one for the ones that start
with the same character and one for the less.
That's overview of the algorithm. So, let's do just a, a quick trace of the
first few recursive calls. So, partitioning item, again, is S.
We divide it up that way. And so now, we're gonna sort the top
subarray, the ones that are less than S. So we partition that out in B and then we
get down to subarrays, size one. And the next thing that we need to do is
the big middle sub-file. We need to sort it on its second
character, so the partition item is E this time.
So we rearrange those to have the ones that start with S, E.
The ones that are less and there aren't any,
And the ones that are bigger. And so next recursion is on the third
letter in that middle subfile. In this case, it's A, and so We have, the
ones that are equal, so that's the ones that start with SEA and the ones that are
bigger of the two cells and then move on to the next character.
So it, it's of the ones that are equal in kind of a controlled way.
That's a example of a trace for 3-way string quicksort.
Now it's a program that almost writes itself.
Once you've seen the idea and you've seen an implementation of Quicksort,
It's a very minor modification into the 3-way quicksort that we discussed when we
were talking about Quicksort. Instead, so we pick out the Dth character.
We take d as an argument, we pick out the dth character we do the regular
Partitioning element. Again, picking out.
Just the Dth character for each key that we look at.
And this is the standard three way partitioning.
And then when we're done with the partitioning, we do the array of ones that
are less chara-, that Dth characters less than the ones that are bigger.
And then in the middle, if we had any, we'd sort the middle sub-ray and we'd move
over one character. That's a, a very compact string sorting
algorithm that performs very well. Now, what about the performance of that
algorithm? Well, we talked about.
Standard quicksort performance. And, if we randomly order the keys ahead
of time. You use 2N natural log int string
compares, on average. And, the thing is, though, if you have
keys that have lots of long common prefixes.
And this happens in lots of applications. Then, those compares are gonna go through
all those keys every time. That 3-way string quicksort Uses, although
the analysis is pretty complicated, it uses only 2N ln N character compares, so
that's an amazing, a huge savings for typical common cases.
It doesn't have to, go through the long common prefixes that usually cause the
problem. And what about versus MSD's or,. Well, MSD sort has this caching problem
and it's got the count arrays and it's got all this overhead involved in maintaining
the counts. Whereas three way string quick-sort is
still cash friendly, 'cause most of the time, it's partitioning the same way that
normal quick sort is. It's still got that short inner loop and
it doesn't use any extra space. And there's all kinds of applications that
for example library call numbers or account numbers where long string keys
that have non randomness in them. This algorithm adapts really well to such
situations. The bottom line is if you've got string
keys, 3-way string quicksort is the method of choice.
It's simple to implement, And it's gonna perform well so I'll
probably leave sorting algorithms with this bottom line.
And the idea is that now we've got a quite fast algorithm that, does a linear
rhythmic number of character compares, And that's in randomly, random keys in
some way. But even if they're not random, it's
difficult to characterize really the worst case.
But it's more, when data is not or this algorithm won't perform well,
And even better chance of getting sub-linear performance then all the other
algorithms. That's 3-way radix quicksort.