The first string sorting algorithm that we're going to look at is actually the
basis for several more complicated algorithms is called key-indexed counting
and it's very useful on a particular special situation. but let's take a quick
review of where we left off with sorting. so we considered a number of sorting
algorithms starting with insertion sort, and then merge sort, quick sort and
heapsort. And we got to the point where we could find an algorithm that's heapsort
that guarantees to sort NL items and time proportional to N log N without using
extra space, unfortunately not stable. And all these algorithms were useful, or are
useful for any type of generic key as long as it implements the comparative
operation. and not only that, we prove that, any algorithm that just uses
compares has to use number of compares proportional to N log base 2N. So, in a
very important sense, merge sort, or heapsort for example, or optimal. you
can't use syntatically fewer compares, for, either one and, and, with heapsort,
you can't use less, extra space. So why do we consider, other sorting algorithms?
there was a lower bound, what, what, why are we thinking about this? And the
question is, can we do better and obviously we're here because, the answer
is that we can do better and if we don't depend on compares. The lower bound, the
one assumption made by the lower bound is that we use compares, but we don't always
need to use compares. And so let's look at an example. Key-indexed counting is a fine
example of that. and it's representative of fairly common situation where, in
sorting application, where it happens to be that the keys that we're using to sort
are small integers. So, in this, this case, this is supposed to mimic an
application where there's students and they're assigned to sections. There's not
too many sections and we want to get the thing sorted. so we want to distribute the
students by section and so we want to sort according to the section number and that's
a small integer. And the implication of knowing that the key is a small integer
is, that we can use the key as an array index and, and by knowing that the key is
an array index, we can arrange for fast sort. so lots of applications for that
when we have maybe a phone numbers, we can sort by area code or if you have a string
you just want to sort by the first letter, you can do it that way. And actually, that
idea leads to efficient sorting algorithm actually two different ways. now don't
forget that we're sorting according to a sort key, but usually we're sorting bigger
generic items that have other information associated with if you were just sorting
the small integers, you could just count how many 1's there are, how many 2's there
are and like that, and then in one path and if there's three 1's, just output
three 1's and so forth. but the complication is that we have to carry the
associated information along so we have to work a bit harder than that. so, here's
the code for this method called key-indexed counting, and, let's look at a
demo. So here's the key-indexed counting demo. Now, to make this a little less
confusing in not so many numbers, we're going to use lower case a for zero, b for
one, c for two and like that. So it's the a - first letter of the alphabet, and
however you want to think of it. so, and we're already going to look at six.
So we're supposing that we're sorting this array that has six different small
integers and we're using lower case letters to represent the integers so that
we can easily distinguish between the keys and this. So now, let's look at, the
processing for this. So the first thing that we do is we go through and we count
the frequency of occurrence of each letter and, so the way that we do that is we keep
an array. now their arrays actually got to be one bigger than number of different
key, keys that we have and the number of different small integers that we have. So
in this case array of size seven. And just this, make the code a little
cleaner, we keep the number of a's in count of one, the number of b's in count
of two and so forth. and s o if we're, once we've set up, that's what we want to
do, then its trivial to go ahead and count the frequencies. we'd simply go through,
for i from zero to N, we'd go through our input. and when we, a of i, when we access
a value in our input, it's a small integer. So it's zero, one, two, three,
four, or five and we simply add one to that integer, and use it to index into
that array. So when we see an a, that's zero, then we're, incrementing count of
one, and we see a b, that's one, we're incrementing count of two and so forth. so
in this case, we increment count corresponding to b and then a and c and
like that. And everytime we encounter a new key, we simply increment one of these
counters. In one pass through we get an array that gives us the number of a's,
b's, c's, d's, e's and f's. That's the first path of key-indexed counting, count
the frequencies of each letter, using the key as an index. now the next step is, is
called computing cumulus, and that's a really easy thing as well. all we do is we
go through the count array and simply at each step we add the current one to the
sum computed so far. So if we look before, we had two a's and three b's, so that
means there's five letters less than c. that's the a's and the b's, and they're
six letters less than d and eight letters less than e and so forth. And that's just
obtained by, we start with two, add three to it, get five, add one to it to get
five. And with that one passed through the count
array, then we can find out for example, there are six keys less than d and eight
keys less than e. And those cumulus tell us where the d's go in the output. There's
six keys less than d, and eight keys less than e, so the d's have to go in a6 and
a7. So this is an array of indices that is going to tell us how to distribute the
keys in the output. So that's the next step, is access the cumulus using the key
as the index to move items. So let's take a look at. So now, remember when we see an
a, we're just going to count that as zero, so we're going to go to count zero and
that will access this entry in the count ar ray.
So, we go through the whole array to be sorted and we move each key exactly to
where it has to go and we'll do that one at, at time now. So when I is zero we're
looking at the d, the count array corresponding to d has six, so it says,
just put d in there and increment that. It means if you get another d, it's going to
go into seven. And these things, the way we pre-computed
them, are not going to run into one another. So now, a, we go, that goes in
zero, and we increment the count array corresponding to a. next thing is c, and
so that's going to says to put it in five and then increment, the count array
corresponding to c, and f, it says put it in nine.
Next is b, we put it in two. Sorry another f, we put in ten.
Next is b that we put in wo. So you can see the keys from the input are getting
distributed in the output according to the counts and the cumulus that we've
pre-computed. so now we get the other d which goes into seven, we get the, another
b which goes into three, and then increment the four for where the next one
goes, f goes into eleven. The last b goes into four, the e goes into
a, and the second a goes into one. So that's move items again, simply by
using the key as index into the count array. and then the last step is to just
copy the sorted array back into the original input. that's a demo of
key-indexed counting. Quick summary of key-indexed counting, we make one pass
through the array to count frequencies of each letter using the key as an index,
then we go through that count array to, compute cumulus just by adding each new
one into the running sum. then we use those cumulates, and access that using key
as index to actually move items over and get them in sorted order, and then move
back into the original array. what's the running time of this algorithm? Well, the
analysis is actually quite simple, because it's just a couple of loops through the
array that we sorted, and through the count array. and the key, key fact to
note, that it takes time proportional to N plus R and space proportional to N + R.
Now R, remember is our array that excess the number of different character values.
so, so for asking, maybe that's the 205th. and, and for generic data maybe it's four.
And N, we're assuming we're sorting huge files. So really, this is linear time in
many, many practical situations. there's also the question of, is it stable? Yeah,
it's actually stable. because when we do the move, we move things with equal keys
in the order that we see them, we keep them in the order that we see them. That's
just the way the method works. So we have for this special situation, we have a
linear time stable sorting method which beats the N log N and it's useful in many
practical situations.