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.
LSD Radix Sort
Loading...
来自 Princeton University 的课程
Algorithms, Part II
416 个评分
从本节课中
Radix Sorts
In this lecture we consider specialized sorting algorithms for strings and related objects. We begin with a subroutine to sort integers in a small range. We then consider two classic radix sorting algorithms—LSD and MSD radix sorts. Next, we consider an especially efficient variant, which is a hybrid of MSD radix sort and quicksort known as 3-way radix quicksort. We conclude with suffix sorting and related applications.
与讲师见面
Robert SedgewickWilliam O. Baker *39 Professor of Computer Science
Computer Science
Kevin WayneSenior Lecturer
Computer Science
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.
