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.