The best sort algorithm we studied so far -- merge sort, quick sort and heap sort take advantage of tree structure thus folding the overall working set's height from N~ish to lgN~ish. O(NlgN) calculation complexity is what we expecting from these sorting algorithms.
Can we do better than that? The answer is symbolism. It is a fancy word of abstraction, as we used all the time in algebra and other goody like various vector spaces to represent quantum mechanics. You need to know all those to understand Radex sort.
It is just a joke to wake you up.
Sometimes we just know too much irrelevant details, if we have an illiterate to read number strings such as 23421, 55555, 1234321, he will have a totally different impression. It is just 10 symbols changing position. If you told that guy you want these symbols to be sorted as 1,2,3,4,5,6,7,8,9 at all the similar positions, that guy beat the best scientist on sorting task.
Now imagine you are that illiterate, try to sort the following space separated numbers. You first have to ask the symbol's order, then you "count as a fool" from right to left following the rule without thinking about what the numbers mean, which is exactly what Radex sort does. Thus you got the best sorting algorithm human-being has discovered so far -- with complexity proportional to n -- O(wn), where w is max length of the string. This is understandable, for each position in a string, you have to visit all the n numbers to get its symbol (then align them into a few arrays in no time as we assume hash table read/write time is constant), there are w possible positions.
δὲ λογοποιία ἐστὶ σύνθεσις ψευδῶν λόγων καὶ πράξεων
Besides, other interesting things might be observed -- for example put same length strings together then count from left to right and some symbol never appeared at the left-most position.
The illiterate might also notice some symbols are more frequent than others, it makes no sense at first glance. However, giving you a Japanese phone book, you will quickly find that symbol 8 is much more frequent than 4, it is just the culture signature coded by the symbol composer. Also the illiterate will notice some symbol combinations are repeated everywhere, they might be the signature of the symbol composer. Computers are the most dumb symbol composer, they use 1 and 0 to express everything.
 |
| radex sort |
0
1
2
3
4
5
6
7
8
9
10
11
function radexSort(a)
{
sortLSD(a, 3);
}
function sortLSD(array, maxDigitSymbols) {
var counter = [[]];
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) {
for (var j = 0; j < array.length; j++) {
var bucket = parseInt((array[j] % mod) / dev);
if (counter[bucket] == null ) {
counter[bucket] = [];
}
counter[bucket].push(array[j]);
}
var pos = 0;
for (var j = 0; j < counter.length; j++) {
var value = null ;
if (counter[j] != null ) {
while ((value = counter[j].shift()) != null ) {
array[pos++] = value;
}
}
}
//update graph
}
return array;
}
<Prev Next>
