A "distribution count" can give you a sorted list, without sorting
anything. And it's faster than any sort algo, clearly, since it's O(n).
Let's say I have a zillion phamlets to pass out along a street. I need
a sorted list of the addresses that get the phamlets, and how many to
give each address.
But I don't need the address list sorted - a bucket sort or
distribution count, is all I need. Since the addresses are all going to
be in a small range, I can fit them nicely into an array and "count"
them up.
On Elm St. I need to drop off phamlet's at: 100(2), 102(1), 105(2),
106(1), 110(3), etc.
but the list is unsorted, like so: 105, 102, 100, 106, 110, 100, 110,
105, 110
Of course, we could sort them, or just "bucket" sort them by counting:
with a zero's out array, I just code:
for(i = 1; i < number_of_addresses; i++) {
//get the next address in the list and
array[address]++;
//increment the count of that address's array index by one
}
Final result is my list, pseudo sorted: array[100] = 2, array[102] =1,
array[105] = 2, array[106] = 1, etc.
So I've got my sorted (sort of), list, and it's all I need to hand out
the right number of phamlets to the proper addresses.
But nothing was actually sorted. It was just a distribution count (or
bucket sort, if you prefer). Won't work for all sorting problems, by
any means, but when it can be used - nothing can touch it.
I agree with you completely about the cache statements you made.
Adak
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
