Radix sort en JavaScript

Question

Yo he llegado con la siguiente pero lo hace predecible no trabajo.

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?
}

Answer 1

Este bucle hace básicamente lo mismo, de una manera más-y 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];
  }
}

En lugar de hacerlo como lo haría un programador de C, este bucle se construye una lista de listas, una lista para cada posible valor de 4 bits. operadores de bits de desplazamiento debo evitar porque se trata de Javascript y mientras lo hacen trabajo , cuando las cosas se ponen divertido números se hacen grandes.

A partir de los bajos 4 bits de cada valor de "a" elemento, las copias de código que de "a" al final de una de las "pilas", que al ser la que corresponde al valor de 4 bits. A continuación, recoge los montones y reconstruye "a" a partir de todos los valores cuya 4 bits bajo eran 0, entonces 1, etc. (Claramente habrá algunas lagunas, por lo que aquellos se omiten.) Al final de cada iteración del bucle en general, el divisor se multiplica por el radix, de modo que será examinado el siguiente conjunto de 4 bits.

Una vez que el divisor ha agotado la gama disponible de números enteros, se hace.

Tenga en cuenta que esto sólo trabajo para positivas los números. Hacer esto con números negativos se hace un poco raro; podría ser más fácil que se deben eliminar los números negativos en una matriz separada, voltear el signo, más o menos, y luego invertir. Ordenar los números positivos y, finalmente, pegar los números negativos inversa (flipping los signos de nuevo) a la parte delantera del ordenadas números positivos.

Answer 2

for(var i = 0; i < count.length; i++) 
{ 
    pref[i] = pref[i-1] + count[i-1]; 
} 

es un problema porque en la primera iteración, i es cero y por lo pref[ 0 - 1 ] no va a funcionar muy bien.

No tengo una referencia de base ordena útil para determinar lo que realmente debería estar haciendo aquí.