My key index counter is a great algorithm but that's not the end of the story.

It's also useful for creating a more general purpose algorithm for strings.

The first one we'll look at is called LSD radix sort, Least Significant Digit for

string sorting. And the idea is a very simple one.

We have strings so we're gonna consider now a small example where the strings are

all the same length. And again that's often true in practical

applications account numbers and so forth. String that uses, sort these, may all be

the same length. And what we're gonna do is consider.

The character positions in the strings, and move from right to left.

The algorithm, is to just stably sort using key index counting, on, the chara-,

deed character of the key, where deed goes from the right end and decreases.

So, this is, a stable sort. Of those twelve keys, sorting on the

right-most character, the B's go before the D's go before the Es.

It's crucial that the sort be stable in this application, and that's why we

checked with key index counting to make sure that it was stable.

So it's a stable sort on, on the right most character.

And then all we do is move from right to left and do now the second character.

And this now is a stable sort of those same keys on the second character.

So now the ones with A in the second character come before the one with B and

so-forth. And not only that, it's stable, so their

relative order is maintained, BAB, CAB, FAD, BAD, and so-forth.

And then. To finish this.

Sort. Now we do it on the first key.

And the magic of LSD radix sorting is eh, once you do it on the first key then the

strings are all sorted. So, that's three passes, one for each

character in the string. Each taking linear time and we get a

string sort. That's LSD sort.

Now we need to prove that it works. And so this is a simple proof by induction

that it worked. After we have done I passes then we can

assume by induction that the strings are sorted on the last I characters.

So we are just showing that for two, after two passes. it sorted on the last two

characters thats we're assuming by induction.

So now what about the next character that we are sorting.

Well, there's two things that can happen. If two strings are different on the first

key, then, the key index sound is gonna do the job.

A string that starts with B is gonna come before one that starts with a D, and so

forth. So if they're different on the sort key,

the key index sort puts them in order. If they're the same on a sort key then

stability does the job. So all the ones with that stay on order

because we've insisted on a stable sort. That's a simple proof by induction that

LSD string sorts fixed length strings in a descending order.

And it's really easy to implement. This is a complete.

Java implementation of LSD string sort. So we're explicitly working with radix

r256. =

256 and where the radix comes in, the value of the radix comes in, is that's the

size of the array that we use for the, counts and the accumulants.

We need one for each character. For each possible character value, we're

gonna index into that array that has to be that big.

And all this is, is the code for key index counting.

And then all we do is take a variable t that goes down from this is the strings of

fixed width w And we start at the rightmost character and go down to the

first character. And instead of dealing with a-ah, our

string A of I2 we're just look at the deed character which is a character.

Otherwise just with that replacement and that replacement it's the same code as we

looked at for key index counting. So let's do key index counting on the deed

character going down from the width from right to left.

That's remarkably compact code. And that's gonna be the method of choice

for lots of situations with fixed length keys as the sort key.

And, and it gives us another look at the performance of sorting out algorithms.

That gives us another line in the table that we're requiring that, that be, they

be fixed length keys, there's ways to work around that.

And we'll consider another algorithm that deals with that in a minute.

But again it's often or typically the case that the.

Width of the keys is not that long. It's a small constant.

And therefore, we have a linear time algorithm.

This even works if the keys are binary numbers represented in a binary word.

We can break them up into groups of small number of bytes Say, 64 byte number can be

broken up into 88 eight bytes characters or four sixteen byte characters.

For sixteen byte characters, W would be four and you can get a huge array of that

kind of numbers sorted in just the four passes through the array.

If they don't have the same length we have to do some extra work.

It's an interesting problem to think about.

We're, we're gonna look at a different method in a minute.

So here's the type of question that somebody might could ask for a job

interview. Actually, a web services company, every

day, might be in the position of needing sort a million or a billion 32 bit or 64

byte integers. And an algorithm student, in interviewing,

might could ask what sorting method do you use?

Now, senator. You hear Google and I like to think of the

presidency as a job interview. Now it's hard to get a job. as president.

Right. And, and you're going through that obviously now.

It's also hard to get a job at Google. Right.

[laugh] We, we have questions. And we ask our candidates questions.

And this one is from Larry Schwimmer. Okay.

[laugh]. You guys think I am kidding?

It's right here. What is the most efficient way to sort a

million 32 bit integers? Well I, no, no, no, no, no, I, I think the

bubble sort would be the wrong way to go. Come on, who told him this?

Okay. I didn't see computer science in the

background. We've got our spies in there.

Well. 'Kay.

Let's ask, let's ask a different interview [laugh] question.

[laugh]. So the bottom line is if you want a good

job maybe, you wanna know about LSD string sort.

Actually, this method has been around for, really a long time.

So we'll start with a little bit of a story.

So what did people do, in the nineteenth century when, they wanted to take a

census? And actually, the story is that, for the

1880 census, it was actually obsolete, before it was completed.

It took 1,500 people seven years to manually process the data.

So, during that time there was room for some invention, and a man named Herman

Hollerith developed an automated machine that could help do the census faster.

So what his idea was to use punch cards to record data.

The kind of data that was taken in the census.

And then the machine could tabulate the data by sorting one column at, at time.

And we'll look a byte at how it does that in just a minute.

And the idea was that the re-, result of that was that the next census finish

really much earlier and under budget, 'cause this machine automated much of the

process. And that had a really a profound effect on

the development of computing 'cause punch cards, it turned out were useful not just

for census but for many other applications.

For accounting and for many other for business processes and for many decades,

punch cards were the primary medium that was used to store, enter, and process

data. And Hollerith's company for building this

machine later emerged with a bunch of other companies.

And in 1924 that company became known as IBM.

And actually, punch cards were used up into the 70's' And even in the 80's' in

some places. So, if, it's important.

Let's take a little break and talk about the role of LSD string sort.

For you know, a couple of decades people who wrote programs were working with

punched cards. And in courses at universities, if you

want to write a program, you wrote it by putting one line on each punched card.

In your program, therefore, was a deck, a long deck of punched cards.

If you had a 1000 line program, you had 1000 punched cards.

They came in boxes that held 2,000, and people would carry around these boxes of

punch cards that, that were their programs.

To enter the program there was a thing called a card punch which had a, which had

a keyboard kind of like a typewriter, but all it did, you could see the cards, and

it'd actually punche holes in the card with what you typed.

Now there was a huge so then, you, you're program was punched cards.

And there was a machine called a card reader which would take the cards in and

convert those punches back into, into binary and characters that again, could be

processed on the computer and then you get your results printed out on paper in a

line printer. So for many, many years people programmed

by making decks of punched cards handing them to an operator who put them on a card

reader and then waiting for the printed output to come out.

There were other devices, but this was the main thing for a long time.

And lots of people learned to program this way.

Now, there was a huge flaw in the system though.

The flaw was, if you dropped the deck, then your program was completely scrambled

and out of order. And you had no program.

You had to go through the cards and find the first line and, then find the second

line. Well, people figured out to work around

for this really almost right from the beginning, cause this is clearly

intolerable, situation, and, the, along with the same room with the card punch,

There was a thing called a card sorter, And the card punch did one other thing

automatically. every time you punched a card.

It would go to the last six columns of the card and it would put in, a number.

Actually they skip by ten So, it would be. The first card would be card ten then

twenty, 30. And your cards would be numbered up to six digits, so you could

have thousands of cards sequentially. So when you typed in your program, you get

the cards numbered, in order. If you wanted to add a few lines to a

program, you had room to add a couple of numbers and, re-punch the numbers, but,

nuh, the whole point was, that all the time when you're holding on to a card

deck, the cards are in order, by number on the right hand column.

And if you dropped it, all you needed to do was sort it.

Or if the m-, machine operator dropped it, that was not viewed as a big deal for your

cards to get [laugh] out of order, because there was this machine that could sort

cards. And the way that it worked was, LSD Rate

exort, the LSD string sort on those characters that are the numbers that keep

the card in order. They would, you'ld start on the right

column. And there was a physical thing, you'd set

to a call and, it was gonna sort on, you put the deck in, and it'd distribute, the

ones with zero in the first bin, or ones with one in the second bin, all the way

up, it'd, and of all the cards it start with zero would come in, and it was

stable, whatever order the cards were in, that's the order they'd appear in the

pile, and then you'd pick them up, and you'd have a new deck, and it'd be all

sorted on the right-most column. Then you move over for one position from

right to left, and run the cards through again.

So if running the cards through the card sorter six times, you could get your deck

sorted. So, every programmer knew LSD radix sort.

For decades, it was not something that was, difficult to teach, 40 years ago.

And, these, this equipment, is now all pretty much gone.

But LSD radix sort, is still a good algorithm to know. Not related is

something else that was going on with those initials at that time.

LSD Radix Sort

Algorithms, Part II

与讲师见面