0:03

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.

Â 3:58

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.

Â