Ordinamento radicale in JavaScript

Question

Ho pensato quanto segue ma prevedibilmente non funziona.

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

Questo ciclo fa sostanzialmente la stessa cosa, in un modo più 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];
  }
}

Invece di farlo come farebbe un programmatore C, questo ciclo crea un elenco di elenchi, un elenco per ogni possibile valore a 4 bit.Evito gli operatori di bit-shift perché questo è Javascript e mentre lo fanno lavoro, le cose si fanno divertenti quando i numeri diventano grandi.

Partendo dai 4 bit bassi di ciascun valore in "a", il codice copia quell'elemento di "a" alla fine di una delle "pile", quella corrispondente al valore a 4 bit.Quindi raccoglie le pile e ricostruisce "a" a partire da tutti i valori i cui 4 bit bassi erano 0, poi 1, ecc.(Chiaramente ci saranno alcune lacune, quindi verranno saltate.) Alla fine di ogni iterazione del ciclo complessivo, il divisore viene moltiplicato per la radice, in modo che venga esaminato il successivo set di 4 bit.

Una volta che il divisore ha esaurito l'intervallo di numeri interi disponibile, il gioco è fatto.

Tieni presente che funzionerà solo per positivo numeri.Farlo con numeri negativi diventa un po' strano;potrebbe essere più semplice eliminare i numeri negativi in ​​un array separato, capovolgere il segno, ordinare e quindi invertire.Ordina i numeri positivi, quindi infine incolla i numeri negativi invertiti (capovolgendo nuovamente i segni) davanti ai numeri positivi ordinati.

Answer 2

questo

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

è un problema perché alla prima iterazione, i è zero e quindi pref[ 0 - 1 ] non funzionerà molto bene.

Non ho un punto di riferimento per Radix ordina a portata di mano per determinare ciò che si dovrebbe in realtà essere facendo qui.