«
»
▶
Lecture Copilot
Lectures
Ask
Exam prep
Help
Sign in
← Introduction to Algorithms (MIT 6.006)
L5
Linear Sorting
Ask the lectures
Every answer cites the moment it comes from. Click a citation to jump there.
Your question
Ask
00:00
Review of search and hash tables
17:43
Direct access array sort
23:58
Tuple sort and digit decomposition
39:37
Counting sort and stability
46:04
Radix sort and polynomial ranges
Transcript
00:00
.
00:12
Good morning, everybody.
00:16
How's everybody doing?
00:18
Nice long weekend we just came from.
00:20
I'm doing well.
00:21
I'm actually getting over a little cold.
00:24
Aw, yeah, unfortunately.
00:27
But after this, I don't have anything else this week.
00:30
So that's good.
00:32
OK, so last time, last week, we talked about how we looked at
00:40
the search problem that we talked about earlier that week
00:48
and showed that in a certain model of computation where I
00:52
kind of could only compare two objects that I'm storing and
01:00
get some constant number of outputs on how I could identify
01:05
these things, like equal or less than or something like that.
01:09
Then we drew a decision tree, and we got this bound that if I
01:14
had n outputs, I would require my decision tree to be at least
01:20
log n height.
01:21
And so in this model, I can't find the things in faster than
01:27
log n time.
01:28
But luckily, we are in a model of computation which has a
01:33
stronger operation, namely random accessing.
01:38
And if we stored the things that we're looking for, we have
01:43
unique keys, and those keys are integers, then if I have an
01:48
item with key k, if I store it at index k in my array, then I
01:58
can find it and manipulate it in constant time.
02:02
That's pretty cool.
02:04
That's what we called a direct access array.
02:06
A direct access array is really not different than a regular array,
02:09
except how we were using it when we were talking about sequences
02:13
is we were giving kind of extrinsic semantics to the slots
02:19
where we were storing these things.
02:21
Basically, I could put any item in any slot, right?
02:26
Where it was in my array had nothing to do with what those
02:28
things were.
02:30
Here, we are imposing intrinsic semantics on my array that if I
02:36
have an item with k k, it must be at index k.
02:42
That's the thing that we're taking advantage of here.
02:46
And then we can use this nice, powerful, linear branching,
02:50
random access operation to find that thing in constant time,
02:54
because that's our model of computation.
02:55
OK.
02:56
Then what was the problem with this direct access array?
03:01
Anyone shout it out?
03:06
Space.
03:07
Right.
03:07
So we had to instantiate a direct access array that
03:12
was the size of the space of our keys, right?
03:15
In general, my index location could go from zero
03:19
to some positive number, right?
03:21
If I have very large positive numbers,
03:23
if I was searching among your MIT IDs,
03:27
I'd have to have a direct access array that spans that space
03:30
of possible keys you could have, right?
03:33
And that could be much larger than n.
03:35
And so the rest of the time, we talked about how
03:39
to fix that space problem.
03:42
We can reduce the space by taking that larger key space
03:46
from zero to u, which could be very large,
03:49
and map it down to a small space.
03:51
Now, in general, if I give you a fixed hash function there,
03:56
that's not going to be good for all inputs.
04:00
If your inputs are very well distributed over the key space,
04:04
then it is good.
04:05
But in general, there would be hash functions with some inputs
04:11
that will be bad, right?
04:12
That's what we kind of argued.
04:14
And so for the rest of the time there,
04:16
we talked about hash families choosing a hash function randomly
04:20
from among a large set of hash functions,
04:24
which had a property that if I chose this thing randomly
04:28
and you, generating your input, didn't know which random numbers
04:32
I was picking, the expectation over my random choice,
04:38
me, I'm the one running the algorithm, not you giving me the input,
04:43
that random choice, my algorithm actually behaves really well
04:47
in expectation.
04:48
In particular, I got constant time for finding, inserting, and deleting
04:54
into this data structure in expectation.
04:57
We did a little proof of that the chain lengths,
05:02
where we stored collisions in our hash function, in our hash table,
05:06
sorry, those wouldn't be very long.
05:10
And so if they were constant, then I don't have to search more
05:14
than a constant number of things when
05:16
I go to a hashed index location.
05:19
Does everyone remember what we talked about last week?
05:22
And we then, I didn't show you this chart at the end,
05:28
but I'm showing it to you now.
05:30
Essentially what we had was we have a bunch of different ways
05:34
to deal with this set interface.
05:37
And last week, we talked about the sorted array,
05:40
and then we talked about this direct access array in this hash table,
05:44
right?
05:45
Which do better for these dictionary, the find and insert and delete operations,
05:54
or at least better in an expected sense, right?
05:58
What's the worst case performance of a hash table?
06:02
If I have to look up something in a hash table,
06:08
and I happen to choose a bad hash function, what's the worst case here?
06:14
What?
06:15
N, right?
06:16
It's worse than a sorted array, right?
06:18
Because potentially I hashed everything that I was storing
06:22
to the same index in my hash table,
06:24
and to be able to distinguish between them,
06:27
I can't do anything more than a linear search, right?
06:30
I mean, I could store another set's data structure as my chain
06:35
and do better that way.
06:37
That's actually how Java does it.
06:39
They store data structure we're going to be talking about next week
06:43
as the chains so that they can get worst case log n.
06:48
But in general, that hash table is only good if we're allowing,
06:54
OK, I want this to be expected good, but in the worst case,
06:58
if I really need that operation to be worst case, right,
07:00
I really can't afford linear time ever for an operation of that kind,
07:05
then I don't want to use a hash table.
07:06
And so on your pset 2, everything we ask you for is worst case,
07:11
so probably you don't want to be using hash tables, right?
07:14
OK.
07:16
Yes?
07:18
What does the subscript e mean?
07:19
That's great.
07:20
In this chart, I put a subscript on this is an expected runtime,
07:27
right?
07:28
Or an a, meaning this is an amortized runtime.
07:31
At the end, we talked about how if we had too many things in our hash table,
07:37
then as long as we didn't do it too often, right,
07:40
this is a little hand wavy argument, but the same kinds of ideas as the dynamic array,
07:44
if whenever we got a linear, we were more than a linear factor away from where we were trying,
07:53
basically the fill factor we were trying to be,
07:56
then we could just completely rebuild the hash table with a new hash function randomly chosen
08:00
from our hash table with a new size, and we could get amortized bounds.
08:05
And so that's what Python, how Python implements dictionaries or sets or even objects when it's trying to
08:12
map keys to different things.
08:17
So that's hash tables.
08:18
That's great.
08:20
The key thing here is, well, actually, if your range of keys is small,
08:26
or if you as a programmer have the ability to choose the keys that you identify your objects with,
08:32
you can actually choose that range to be small, to be linear, to be small with respect to your items,
08:39
and you don't need a hash table.
08:40
You can just use a direct access array, right?
08:43
Because if you know your key space is small, that's great.
08:48
So a lot of C programmers probably would like to do something like that,
08:51
because they don't have access to, maybe C++ programmers would have access to their hash table.
08:58
Any questions on this stuff before we move on?
09:00
Yeah?
09:07
Why is it expected, right?
09:08
When I'm building, I could insert, I'm inserting these things from x one by one into my hash table.
09:16
Each of those insert operations, I potentially have, I'm looking up to see whether that,
09:22
an item with that key already exists in my hash table.
09:24
And so I have to look down a chain to see where it is.
09:28
However, if I happen to know that all of my keys are unique in my input,
09:34
right, all the items I'm trying to store are unique,
09:36
then I don't have to do that check and I can get worst case linear time.
09:40
Does that make sense?
09:41
All right.
09:42
It's a subtlety, but that's a great question.
09:45
OK.
09:45
So today, instead of talking about searching, we're talking about sorting.
09:50
OK.
09:51
Last week, we saw a few ways to do sort.
09:57
Some of them were quadratic, insertion sort and selection sort.
10:00
And then we had one that was n log n.
10:02
And this thing, n log n, seemed pretty good, but can I do better?
10:09
Right?
10:10
Can I do better?
10:12
Well, what we're going to show at the beginning of this class is,
10:16
in this comparison model, no.
10:19
n log n is optimal.
10:20
And we're going to go through the exact same line of reasoning that we had last week.
10:25
So in the comparison model, what did we use when we were trying to make this argument that any
10:41
comparison model algorithm was going to take at least log n time?
10:48
What we did was we said, OK, I can think of any model in the comparison model,
10:52
any algorithm in the comparison model, as kind of this, some comparisons happen.
11:01
They branch in a binary sense, but you could have it generalized to any constant branching factor.
11:07
But for our purposes, binary is fine.
11:10
And what we said was that there were at least n outputs, really n plus 1, but, you know,
11:17
at least order n outputs.
11:19
And we showed that, or we argued to you, that the height of this tree had to be at least
11:28
log n, right?
11:31
Log the number of leaves.
11:33
It had to be at least log the number of leaves.
11:36
That was the height of the decision tree.
11:38
And if this decision tree represented a search algorithm, I had to walk down and perform these
11:47
comparisons in order, reach a leaf where I would output something.
11:51
So I need, if the minimum height of any binary tree on a linear number of leaves is log n,
12:02
then any algorithm in the comparison model also has to take log n time, because it has to do that
12:11
many comparisons to differentiate between all possible outputs.
12:15
Does that make sense?
12:18
All right.
12:18
So in the sort problem,
12:26
how many possible outputs are there?
12:31
What is the output of a sorting algorithm?
12:32
What?
12:41
What's up?
12:42
A list.
12:43
In particular, given my input,
12:47
like some set of items A that has size n,
12:53
What I'm going to give you is some permutation of that list.
13:00
So for each index, say, I could tell you where it goes.
13:09
Another way I could say is where does the first item go to?
13:15
Where does the second item go to?
13:16
Where does the third item go to?
13:18
Blah, blah, blah, blah, like that.
13:21
So how many different choices of a permutation are there?
13:25
Well, how many choices do I have for the first thing of where
13:29
it could be in the final sorted array?
13:31
It could be in any of the places, right?
13:34
So it's n.
13:36
How about this one, the second one?
13:38
Well, it can't go to where this one went, right?
13:42
But it can go anywhere else.
13:43
So it's n minus 1.
13:45
And since these are independent choices I'm making,
13:47
if I multiply them all together I get n factorial permutations
13:51
that are the number of possible outputs that I have
13:54
to my sorting algorithm, right?
13:55
So for me to have an output to my sorting algorithm be correct,
13:59
I need at least n factorial leaves.
14:01
Does that make sense?
14:03
OK.
14:07
The nice thing about doing this last week
14:10
is this is really just the number of leaves.
14:14
And this is really the number of leaves, right?
14:16
So what's the number of leaves?
14:19
It's theta n factorial.
14:21
Here it's actually n factorial, but I'm just going to put it there.
14:25
And here we get an n factorial.
14:27
I think this is, I see.
14:33
So it's at least omega n factorial.
14:39
Does that make you happy?
14:42
Theta here.
14:42
Thank you.
14:44
Has to be at least.
14:47
So this was right.
14:50
OK.
14:51
So at least this many.
14:52
I could, there are algorithms that if it got to,
14:57
it could take two different routes to get to the same output, right?
15:00
So this is a lower bound on the number of leaves.
15:03
OK.
15:05
So what this argument is saying is that if I just
15:08
replace the number of leaves n here with n factorial,
15:11
I get a similar comparison sort lower bound now.
15:15
So what is log of n factorial?
15:17
Is this familiar from pset one, maybe?
15:24
So one thing I could do is I could put in Sterling formula,
15:28
right?
15:32
And that'll give me something of the form n log n.
15:35
But what's another way I could lower bound n factorial?
15:41
Well, I have a bunch of things here.
15:42
That's n factorial.
15:48
Half of these things, these half, n over two things,
15:54
are bigger than or equal to n over two.
15:58
Does that make sense?
16:00
So I can certainly lower bound this thing
16:04
by n over two to the n over two.
16:08
That's a little easier thing to take a log of, right?
16:11
If you take a log of that, that's asymptotically n log n.
16:17
So what we're getting here is any sorting algorithm here
16:20
takes at least n log n comparisons.
16:24
And so merge sorts the best we can do.
16:26
OK?
16:28
Does that make sense to everybody?
16:30
We're just piggybacking on the analysis we had about decision
16:33
trees connecting leaves with the minimum height of any binary tree
16:40
on that number of leaves.
16:43
And just replacing n with n factorial.
16:46
Nothing super interesting here.
16:48
Yeah?
16:49
.
16:51
Yeah, sure.
16:52
You can just plug in Sterling formula, but I did this, so I might as well clarify.
16:57
There are n terms here in the product, right?
17:03
Half of them are at least n over two.
17:06
Does that make sense?
17:08
So I can replace, I can lower bound this product by something smaller than half of the terms,
17:15
a product of that.
17:16
And that would be fine, right?
17:18
So I'm taking n over two of them, and I'm multiplying n over two altogether, n over two
17:24
times.
17:25
Does that make sense?
17:28
OK.
17:29
It's just providing a lower bound, right?
17:31
I just need something that's smaller than all of these terms.
17:34
And multiply them all together.
17:35
And that'll give me a lower bound.
17:39
OK.
17:40
So we can't do better than n log n in the comparison model.
17:43
But what we did last week was use random access and a direct access array to do better.
17:49
OK?
17:50
So can anyone think of how to use that idea to sort faster?
17:57
And I'm going to give you a caveat here.
18:00
I'm going to let you assume that the keys of the things you're trying to sort are unique.
18:07
OK?
18:08
And say they're in a small range.
18:13
So how could I use a direct access array to sort faster?
18:18
Any ideas?
18:20
Yeah?
18:21
So you literally can start to do like a different aspect.
18:26
Uh-huh.
18:27
And then you look at that array and that'll sort.
18:31
OK.
18:32
So what your colleague is saying is exactly correct.
18:34
It's something that I like to call direct access array sort.
18:37
We won't really call it that because there's something more general that we'll talk about
18:43
in just a second.
18:45
But what your colleague was saying is instantiate a big direct access array.
18:50
Direct access array sort.
18:54
Right?
18:56
I'm instantiating this big direct access array of the space of my keys.
19:02
Right?
19:03
And what your colleague was saying was I take each one of the items in my, the things that
19:09
I'm trying to sort.
19:10
I look at each one of their keys.
19:11
And I stick it in the direct access array exactly where it needs to go.
19:18
Right?
19:19
In constant time.
19:20
That's great.
19:22
Now, I gave you this caveat that all the keys were unique.
19:24
So I don't have to deal with collisions here.
19:26
Right?
19:27
But then after I'm done with this, all of these things are now in sorted order.
19:31
And what I can do is I can just walk down this list.
19:36
A lot of these cells are empty, potentially.
19:39
Right?
19:40
Well, some of the keys might not be there.
19:43
But what I can do is just walk down this list, pick off every item that does exist, stick
19:50
them in an array, I'm done.
19:52
Right?
19:53
So what's the stick a key into here?
19:58
And then, so, all right, make direct access array, store items, item x in index x dot key,
20:25
walk down direct access array, and return items seen in order.
20:41
Does that make sense to everybody?
20:44
All right.
20:45
How long does this step take?
20:53
Building a direct access array, order u.
20:57
Okay, so this is order u.
21:00
How long does this take?
21:05
How many items do I have to insert?
21:07
Order n, or just n.
21:10
And how long does it take to insert each one of these things into my direct access array?
21:16
Worst case constant time.
21:18
Right?
21:19
So this is n times worst case constant time.
21:24
Great.
21:25
How long does this last one take?
21:27
Anyone?
21:28
O of u also, right?
21:29
Because I'm walking down the entire length of u.
21:33
So this algorithm takes, in total, n plus u time.
21:48
This is great.
21:49
If u, u is bigger than n because we assume distinct keys, right?
21:55
But if u is on the order of n, then we now have a linear time sorting algorithm.
22:03
Yes?
22:04
What's up?
22:05
I'm sorry, you have to speak up.
22:11
How do you attach keys to element to the vector in the direct order?
22:15
How do I attach keys to my inputs?
22:19
So, for a set data structure that we've been talking about, all of my items have keys.
22:26
That's just something that we impose on our input.
22:33
Each of the keys is, in this case, it has to be a number.
22:37
Right?
22:38
So, that's a nice point, right?
22:41
We do this to kind of talk about sorting items generally so that we don't have to deal
22:48
with, potentially, if these keys have values associated with it or other stuff associated
22:52
with it.
22:53
We don't have to find that item and they'll still be there.
22:55
But, in general, if you just wanted to sort integers, you could say that dot key points
23:02
back to the object itself if you want to just sort some integers.
23:05
Does that make sense?
23:06
It's a good question, though.
23:08
Okay.
23:09
So, that gives us a linear time algorithm when u is small, right?
23:14
And, under this condition that I have unique keys when I want to sort, right?
23:19
Those are fairly restrictive, so we might want to generalize this a little bit.
23:24
Okay?
23:25
So, that's direct access array sort.
23:28
What if we had a set of keys that was a little larger?
23:34
Right?
23:35
So, instead of enforcing, so let's say u is theta n implies linear time sorting.
23:52
That's great.
23:53
Okay?
23:54
So, now, what happens if we expand that range a little bit?
23:58
Let's say u is less than or equal to n squared.
24:02
Maybe just less than.
24:03
Okay?
24:04
Okay.
24:05
This is a bigger range, right?
24:08
And, if we instantiated a direct access array of quadratic size, we'd have a quadratic time
24:19
algorithm.
24:20
This is not helpful.
24:21
Right?
24:22
So, anyone have a way in which we could sort integers that are between 0 and n squared?
24:35
Maybe using the stuff that we had above.
24:40
Yeah?
24:41
Could you perhaps like sort by the first n, kind of like the first digit?
24:47
Ah!
24:48
Your colleague is saying exactly the thing that I'm looking for, which is great.
24:54
Which is, maybe we could break this larger number into two smaller numbers.
25:03
Right?
25:04
Any integer that is between 0 and n squared can be written as key, can be sum a and b, where
25:19
a is essentially the higher kind of n, and b is kind of the lower n.
25:28
This is kind of weird.
25:30
Okay.
25:31
So, what do I actually mean by this?
25:32
I mean that, let's let a be k, when I divide it by n, integer, the floor, right?
25:45
Key integer to divide by n, right?
25:51
And b equals k mod n.
25:56
So, this is a number that's less than n, and this is a number that's less than n.
26:02
Does that make sense?
26:03
Does that make sense?
26:04
And actually, I can recover k at any time by saying k equals a n plus b.
26:12
I've essentially decomposed this into a base n representation of this number.
26:19
And I have two digits in that number.
26:20
And I have two digits in that number.
26:23
This is the kind of n digit, and this is the ones digit.
26:28
Does that make sense?
26:30
All right.
26:31
All right.
26:32
So, now let's say I have this list of numbers.
26:43
17, 3, 24, 22, 12.
26:53
I could, here I have five numbers.
26:56
So, what's n in this case?
26:57
5.
26:58
Okay.
26:59
Not so interesting.
27:00
n is 5 here.
27:03
And I'm going to represent this as five pairs of numbers that are each within the bounds of
27:12
0 to 4, right?
27:14
Does that make sense?
27:15
Does that make sense?
27:16
So, what is my a, b representation of 17?
27:20
3, 2.
27:25
Okay.
27:26
So, yeah.
27:28
So, there are 3 times 5 plus 2.
27:34
That's good.
27:35
That's 17.
27:36
Yeah?
27:37
I think your colleague did that right.
27:40
I have all of these written down, so I'm just going to write it out.
27:53
And I hope I did it correctly.
27:55
Okay.
27:56
3, 2.
27:57
0, 3.
27:58
4, 4.
27:59
4, 2.
28:00
2, 2.
28:01
Okay.
28:02
So, now I have a bunch of things that I want to sort.
28:06
Based on this function that I have, right?
28:11
These are no longer just integers that I need to sort.
28:14
I need to sort by this transformation of this thing into a number.
28:19
Does that make sense?
28:21
So, anyone have any ideas on how we could sort?
28:26
By the way, these are both constant time operations on your computer, as long as it's an integer
28:34
division, right?
28:35
And this is mod.
28:37
Python also has a nice thing, I think, in its standard operations, which is div mod of kn.
28:50
Is that right?
28:51
Yeah.
28:52
So, if you want to use that, you can.
28:56
Okay.
28:57
So, how do we sort these tuples?
28:59
These are tuples, right?
29:01
You guys are, I'm sure, very familiar with tuples by now.
29:07
Okay.
29:08
How do I sort these tuples?
29:14
What's the most important digit of this thing?
29:17
If I add to sort one of the digits and get something that's close to sorted, what's more important?
29:24
The ones digit or the n's digit?
29:26
Okay.
29:27
We have discrepancy here.
29:30
Who says one?
29:32
Who says n?
29:33
Someone who said n, tell me what?
29:36
Oh, you all think that way for no reason.
29:43
Yeah.
29:44
Sorry.
29:45
This is a little confusing.
29:48
This is the ones digit.
29:50
This is the n's digit.
29:51
This is the n's digit.
29:52
This is the n's digit.
29:53
This is the ones digit in how I'm writing this.
29:56
Does that make sense?
29:57
Yeah.
29:58
These different n's digits have like, that are the difference on the digit inside of it.
30:03
So, you can have like, you can present to each other, but that only tells you like, where
30:07
they are with regard to the specific n category there is.
30:11
Exactly.
30:12
Yeah.
30:13
So, what your colleague is saying is exactly correct.
30:16
I could vary b all I want, right?
30:20
With the same a.
30:22
If I change a by one, it doesn't matter what b is, it's going to be bigger.
30:27
Right?
30:28
Does that make sense?
30:32
Right?
30:33
The k is much more sensitive to a than it is to b.
30:37
Right?
30:38
So, a is more important than b.
30:39
Does that make sense?
30:41
So, if I just wanted to get some linear time algorithm, I could just sort by their bigger
30:48
digits and hope they don't differ very much on the smaller things.
30:54
I've kind of sorted these things.
30:56
Does that make sense?
30:57
Okay.
30:58
What if I actually want to sort these things?
31:01
Any hands?
31:05
Yeah.
31:07
I need to sort on both in some sense.
31:13
In particular, I like to think of what I'm going to tell you right now is an algorithm
31:20
that I like to call tuple sort.
31:22
But you can also think of it as like Excel spreadsheet sort.
31:26
Right?
31:27
I have an Excel spreadsheet of a bunch of data.
31:30
I have a prioritization on how important the keys are to me, the columns.
31:34
Right?
31:35
And if I have a very important column, and an order of the columns of how important they
31:43
are to me, I can repeatedly sort on the columns until they're sorted based on my preference.
31:52
That's something that you may have done.
31:55
Now, if I have an ordering on the preferences of my columns, do I start by sorting all of
32:02
them on the most important thing or the least important thing?
32:07
What?
32:08
Who says most?
32:11
Who says least?
32:14
There's discrepancy here.
32:17
All right.
32:19
Let's try it out.
32:21
All right.
32:22
Tuple sort.
32:25
Let's start by sorting these things by least significant first and then least significant.
32:35
That was the first thing I asked you.
32:37
Right?
32:38
All right.
32:39
So these are the most significant things, the first ones.
32:42
And these are the less significant things.
32:45
All right.
32:46
So instead of writing it as tuples, I'm going to write them as 32, 0, 3, 44, 42, 22.
32:54
Is everyone cool with that?
32:55
This is just base 5 representation.
32:57
OK?
32:58
All right.
32:59
So let's start by sorting all of these things by the most significant thing.
33:06
Right?
33:07
Which is by this guy, this guy, this guy, this guy, and this guy.
33:10
OK.
33:11
So how do I do it?
33:12
The first one is 0, 3.
33:14
The second one is 22.
33:17
The next one is 32.
33:20
42.
33:21
And then 44.
33:25
Maybe 44.
33:27
I don't know.
33:28
Does it matter?
33:30
The order in which I put these things?
33:32
I don't know.
33:33
I'm just going to keep it the same order for now.
33:35
All right.
33:36
So I've sorted it by the least significant, or the most significant.
33:39
Sorry.
33:40
The leading term.
33:41
And now I'm going to sort by the least significant.
33:45
So what's the least significant here?
33:48
22.
33:49
Then 2 is also.
33:52
This is also 2.
33:54
This is also 2.
33:55
This is 3.
33:57
And sorted list.
34:00
Voila.
34:01
Why did that not work?
34:04
Yeah.
34:05
So what happened is I did take into account the significant digit sort.
34:22
But when I did the less significant thing, it erased all of my work from up here.
34:27
Does that make sense?
34:28
In the case of ties, we want the more significant thing to take precedence.
34:36
So we want to do that thing last.
34:38
Does that make sense?
34:40
So the right way to do this, this is most significant first.
34:48
Add.
34:49
Okay.
34:50
Not good.
34:51
All right.
34:52
Least significant first.
34:53
Let's try that.
34:55
So least significant here is 2.
35:01
Okay.
35:02
So I see 32, 42, 22, 03, and then 44.
35:16
Okay?
35:17
Sound good?
35:18
Least significant first.
35:20
Now I do most significant.
35:23
I sort the most significant thing.
35:24
Okay.
35:25
So what's the most significant thing?
35:27
0, 3, 22, 32, most significant 4, 44, and 42.
35:39
Cool.
35:40
We're sorted, right?
35:41
I did what you told me to do.
35:42
I sorted by the most significant thing.
35:43
What's the problem here?
35:44
What did I do wrong?
35:45
You wanted me to put 42 here and 44 here, right?
35:48
Because 42 came first in the input and 44 came second, right?
35:54
Okay.
35:55
Okay.
35:56
If the sorting algorithm maintains this property, that if they are the same thing, right?
36:09
4 came second, right?
36:14
OK, if a sorting algorithm maintains this property,
36:18
that if they are the same thing, right,
36:22
then the output maintains their order
36:27
from the input to the output, their relative order.
36:31
That's what we call a stable sorting algorithm, right?
36:34
And so if we have a stable sorting algorithm
36:36
when we're doing tuple sort, when we're
36:39
sorting on different keys or columns of a set, right,
36:44
we really want to be using a stable sorting algorithm.
36:48
Does that make sense?
36:50
Because otherwise, we may mess up work we did before
36:54
in a previous sort of the less significant things.
36:58
And so yes, we want a stable sorting algorithm here,
37:04
because then we will end up sorting our thing.
37:08
Does that make sense?
37:10
Yes?
37:10
What prevents us from sorting by most significant,
37:13
and then simply simply echoing the relevant
37:16
to each chunk?
37:17
So what your colleague is saying, let's sort by most significant,
37:23
then look at all of the things with one of those that are the same,
37:29
and now sort that.
37:32
That's something we could do.
37:34
OK?
37:34
How long would that take?
37:35
Well, let's say I didn't use half of my more significant set of digits, right?
37:44
Say I'm only using n over 2, or that's not quite going to get what I want.
37:58
Say again?
37:58
Say again?
37:59
.
38:00
So what we're going to do if we have direct access array sort,
38:06
if I then go into each one of these digits and try to sort the things that are in there,
38:11
that's going to take time, right?
38:12
It's going to take time per each of those digits.
38:14
Now, there might be a ton of collisions into one of the things,
38:20
and so I might take more time to sort that than linear.
38:25
Does that make sense?
38:26
So I would prefer to do this tuple sort kind of behavior,
38:30
sorting the smaller thing, sorting the bigger thing.
38:33
And because I only have a constant number of things in my tuples,
38:36
this is important, because I only have two things I'm worried about here,
38:41
I only have to do two passes of a sorting algorithm to be able to sort these numbers.
38:51
However, can I use direct access array sort here?
38:56
What was the initial stipulation I had on direct access array?
39:00
That the keys were unique.
39:03
That's exactly the opposite of what we have here.
39:05
We have things that could be the same.
39:06
So we give up.
39:11
Can't do it.
39:16
What do we do instead?
39:17
We, yeah?
39:21
.
39:29
You've already said the thing that I'm looking for, so that's great.
39:32
Your colleague said, why can't we just put more things at a key?
39:37
Right?
39:38
Why can't we put a list there?
39:41
That's exactly what we do.
39:42
This is called counting sort.
39:48
And what we do here is we still have this direct access array,
39:51
and we're going to put a space u minus 0 to u minus 1.
39:56
But instead of storing one thing here,
40:01
at each key k, we store a pointer to a chain.
40:07
This sounds like hashing, right?
40:10
But the important thing is that I need to make sure,
40:14
as I'm inserting things in here,
40:16
then I'm maintaining the order in which they came in.
40:19
Right?
40:20
I can't just throw them willy-nilly,
40:21
or else we have this problem up here that we had before.
40:23
Right?
40:24
So I need what I would say is a sequence data structure.
40:28
Right?
40:29
Something that will maintain the order that I,
40:31
the extrinsic order that I had when I'm putting these things in.
40:34
Right?
40:35
So as I have multiple things with k, right,
40:43
I'm going to put them in the order.
40:45
I can basically, I can put, have a pointer to a dynamic array,
40:48
or a linked list, where I just add things to the end.
40:52
And then at the end of my algorithm,
40:54
when I read off the things,
40:57
I can just look at anyone that has a non-empty data structure under here,
41:03
and read them off in the order that they came.
41:06
Does that make sense?
41:08
So for this example,
41:13
I'm just going to do this last step here,
41:17
from the first row to the second row.
41:21
I'm going to have this direct access array
41:24
with 0, 1, 2, 3, 4 on the slots.
41:29
Right?
41:31
So how am I going to do this counting sort now?
41:35
I have 32, 42, 22, 0, 3, and 44.
41:41
I'm going to take the first one, 32.
41:43
I'm sorting by the most significant thing.
41:45
I stick it here.
41:47
32.
41:49
And then 42, 4.
41:52
Okay, 42.
41:54
Sorry.
41:55
42.
41:56
All right.
41:57
This is not so much different yet than dynamic array,
42:06
direct access array sort.
42:08
But when we get to this duplicate,
42:11
right, 44 here,
42:16
we now have two things in this thing.
42:19
And because we are keeping them in order in this sequence,
42:23
I'm appending to the end.
42:25
Then when I go and read off the different things,
42:29
then I'm returning them in a stable way,
42:33
in the way that I want them to be.
42:36
Does that make sense?
42:37
And it's not overriding the work I did on the lower significant digits.
42:42
Okay?
42:43
So how long does this take?
42:45
This also only takes order n plus u.
42:52
Because I'm instantiating this thing of size u.
42:59
And then how big are these data structures?
43:02
Well, maybe I'm storing one,
43:04
a constant amount for each index.
43:07
So that's a u overhead.
43:09
And then I'm paying one for every item I'm storing.
43:12
Right?
43:13
These things are only the lengths.
43:17
The sum total of their lengths is n.
43:20
Right?
43:21
Because I'm only storing n things in there.
43:24
So the total amount of space,
43:29
the total amount of work I have to do is order n.
43:32
I need to be able to append in constant time.
43:35
And I need to be able to cycle through these things,
43:38
iterate over them in linear time.
43:40
But if I have that, I get n plus u.
43:42
Yeah?
43:43
How do you ensure that with this, like your length list,
43:46
or like your dynamic, like those elements, like 4, 3, 4, 4,
43:51
how do you ensure that those are sorted?
43:54
Ah.
43:55
So your colleague is saying,
43:58
how do I ensure that the things in these lists,
44:01
that they're there collide,
44:02
how do you ensure that they're sorted?
44:03
I don't.
44:04
I just ensure that they came in in the order that they came.
44:08
Right?
44:09
But as long as I sorted the lower order digits correctly in the previous things,
44:16
then I'm assuming that their order as they come in will be sorted if they collide.
44:22
That's the assumption, that's the reason why I'm doing these,
44:26
building up from the least significant to the most significant.
44:29
It's so that I know that when they collide,
44:33
the underlying stuff there is sorted already in the input.
44:37
Does that make sense?
44:38
Great.
44:39
Yeah?
44:40
So this array isn't asking as u, it's asking as n.
44:47
So this one is still, I'm using a direct access array on the keys,
44:50
though this is n.
44:52
This is n because I chose,
44:55
so counting sort is general for any u.
44:58
I just happened to pick u being n in this case,
45:03
when I broke this thing up into n squared.
45:05
But this general concept is,
45:08
it doesn't matter what I choose for u.
45:11
Does that make sense?
45:13
OK.
45:15
But we will use that right now to sort larger ranges of numbers.
45:20
OK?
45:22
So, the idea here, this was exactly the idea.
45:26
We're going to combine tuple sort, use counting sort as its auxiliary sorting,
45:31
stable sorting algorithm,
45:33
to do all its work on these digits.
45:36
And so, to sort on n squared size numbers, I get linear time,
45:45
which is great, right?
45:47
Because u is n in this case.
45:49
OK?
45:50
So, but can I extend that?
45:55
What if I had n cubed?
45:57
What if I had up to size u equals n cubed, or less than n cubed?
46:04
How many digits would I have there?
46:07
How many size n digits would I need to represent a number of size n cubed?
46:21
Any ideas?
46:22
What did we do here?
46:25
We divided off an n.
46:27
We took it and stored it.
46:29
We're left with something of size n, right?
46:32
If I had a number of size n cubed, I could divide off an n.
46:36
I'm left with something of n squared.
46:38
I don't know how to deal with something of n squared.
46:40
Actually, I do.
46:41
What did I do?
46:42
I can split it up into two size n numbers, right?
46:46
So, if I had numbers bound, upper bounded by a cubic, right, n cubed,
46:53
I could split it up into three digits.
46:55
Three is still constant, right?
46:57
And so I could split it up into three digits,
47:01
tuples sort them in their increasing priority, and sort those.
47:07
Again, I'm doing linear work per digit.
47:10
I have a constant number of digits, so I get a linear time algorithm.
47:13
Yeah?
47:14
When you come to the store, you can see the unit.
47:17
How are you ensuring that the nan run time is also big O of n plus u?
47:23
Yeah, so it's always going to be big O of n plus u,
47:27
but because I'm bounding my digit size to be n, u is n there,
47:34
and so I'm getting linear time.
47:35
Does that make sense?
47:36
Yeah.
47:37
Yeah, so the idea here, this is what we call radix sort.
47:41
Radix sort.
47:44
Break up integers, max size u, into a base.
48:04
A base n tuple.
48:10
Right?
48:12
So basically, each one of my digits can range from 0 to n, right?
48:17
How many digits do I have if I have, how many base n digits do I have if I have a number of size u?
48:24
Yeah, log n of u.
48:29
Number of digits is log n of u.
48:36
Log base n of u, right?
48:39
So how long does ray n n tuple sort on digits using counting sort?
48:52
From least to most significant, right?
49:05
That's the algorithm.
49:06
How long does that take?
49:09
How long does it take to sort on a digit that spans the keys 0 to n?
49:15
Linear time, right?
49:18
Order n time.
49:19
How many times do I have to do this tuple sort?
49:23
The number of digits times, right?
49:26
So the running time of this algorithm, first I have to, you know, I have to do this stuff.
49:33
Break up each of the integers.
49:35
That takes n time, right?
49:37
N times the number of digits.
49:38
I had to create each one of these tuples, right?
49:41
So n plus n times the number of digits, right?
49:47
Log base n of u, right?
49:54
So here, I had to loop through all the things.
49:57
And then here, for each thing, I broke it up into log base n of u digits.
50:08
And that's how long the first thing took.
50:11
And then how long did it take me to tuple sort?
50:14
N time per digit.
50:17
So I also get this factor.
50:19
Does that make sense?
50:22
So how long is that?
50:24
Is that good?
50:25
Is that bad?
50:26
For what values of u is this linear time?
50:31
If u is less than n to the c for some constant c, then this c comes out of the logarithm.
50:45
Log n of n is 1.
50:48
And we get a linear time algorithm.
50:50
Does that make sense?
50:52
OK, so that's how we can sort in linear time if our things are only polynomially large, right?
51:00
So in counting sort, we get n plus u.
51:03
In radix sort, we get also a stable sorting algorithm where the running time is n plus n times log base n of u.
51:13
Does that make sense?
51:16
And then, in the situations where there's a typo there in counting sort, that should be when u is order n, counting sort runs in linear time.
51:27
And it's linear time also, in the case of rating sort, if our things are bounded by a polynomial in n, right?
51:35
By n to the c for some constant c.
51:38
Does that make sense?
51:40
All right, so that's how to sort in linear time with the caveat that your numbers aren't too big.
51:47
OK, see you next week.