Radix Sort em JavaScript
-
26-09-2019 - |
Pergunta
Eu criei o seguinte, mas previsivelmente não funciona.
var t = new Array(a.length);
var r = 4;
var b = 64;
var count = new Array(1<<r);
var pref = new Array(1<<r);
var groups = Math.ceil(b / r);
var mask = (1 << r) - 1;
var shift = 0;
for(var c = 0; c < groups; c++)
{
shift += r;
for(var j = 0; j < count.length; j++)
{
count[j] = 0;
}
for(var i = 0; i < a.length; i++)
{
count[ (a[i] >> shift) & mask ]++;
}
pref[0] = 0;
for(var i = 0; i < count.length; i++)
{
pref[i] = pref[i-1] + count[i-1];
}
for(var i = 0; i < a.length; i++)
{
t[ pref[ (a[i] >> shift) & mask ]++ ] = a[i];
}
for(var i = 0; i < a.length; i++)
{
a[i] = t[i];
}
// a is sorted?
}
Solução
Esse loop faz basicamente a mesma coisa, de uma maneira mais JavaScript:
for (var div = 1, radix = 16; div < 65536 * 65536; div *= radix) {
var piles = [];
for (var i = 0; i < a.length; ++i) {
var p = Math.floor(a[i] / div) % radix;
(piles[p] || (piles[p] = [])).push(a[i]);
}
for (var i = 0, ai = 0; i < piles.length; ++i) {
if (!piles[i]) continue;
for (var pi = 0; pi < piles[i].length; ++pi)
a[ai++] = piles[i][pi];
}
}
Em vez de fazer isso como um programador C, esse loop cria uma lista de listas, uma lista para cada valor possível de 4 bits. Eu evito operadores de deslocamento de bits porque este é JavaScript e enquanto eles o fazem trabalhar, as coisas ficam engraçadas quando os números ficam grandes.
Começando com os 4 bits baixos de cada valor em "A", o código copia esse elemento de "A" para o final de uma das "pilhas", sendo esse o correspondente ao valor de 4 bits. Em seguida, ele reúne as pilhas e reconstrói "A" a partir de todos os valores cujos 4 bits baixos foram 0, então 1, etc. (Claramente haverá algumas lacunas, então essas são ignoradas.) No final de cada iteração Do loop geral, o divisor é multiplicado pelo Radix, para que o próximo conjunto de 4 bits seja examinado.
Uma vez que o divisor esgote a gama disponível de números inteiros, está feito.
Observe que isso só funcionará para positivo números. Fazer isso com números negativos fica um pouco estranho; Pode ser mais fácil retirar os números negativos em uma matriz separada, girar a placa, classificar e depois reverter. Classifique os números positivos e, finalmente, cola os números negativos invertidos (virando os sinais novamente) na frente dos números positivos classificados.
Outras dicas
isto
for(var i = 0; i < count.length; i++)
{
pref[i] = pref[i-1] + count[i-1];
}
é um problema porque na primeira iteração, i
é zero e assim pref[ 0 - 1 ]
não vai funcionar muito bem.
Não tenho uma referência para a Radix Tinds Handy para determinar o que você realmente deveria estar fazendo aqui.