Radix Sort in JavaScript

Question

Ich habe mit dem folgenden kommen, aber es tut vorhersagbar nicht.

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

Diese Schleife funktioniert im Grunde das gleiche, in einer Javascript-y Art und Weise:

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];
  }
}

Statt es wie ein C-Programmierer könnte tun, baut diese Schleife eine Liste von Listen, eine Liste für jeden möglichen 4-Bit-Wert. Ich vermeide Bit-Shift-Operatoren, denn dies ist Javascript und während sie Arbeit , werden die Dinge lustig, wenn Zahlen groß werden.

Beginnend mit den niedrigen 4 Bits jeder Wert in „A“, die Code Kopien, die Bestandteil der „a“ an das Ende einer der „Haufen“, das ist die, entsprechend dem 4-Bit-Wert. Es sammelt sich dann die Pfähle und neu aufgebaut „A“ von allen Werten, deren niedrigen 4 Bits waren 0 beginnt, dann 1 usw. (Offensichtlich gibt werde einige Lücken, so dass diejenigen, werden übersprungen.) Am Ende jeder Iteration der Gesamtschleife wird der Divisor vom radix multipliziert, so daß der nächste Satz von 4 Bit untersucht werden.

Wenn der Divisor den verfügbaren Bereich von ganzen Zahlen erschöpft hat, es gemacht wird.

Beachten Sie, dass dies nur funktioniert, für positive Zahlen. Dadurch mit negativen Zahlen wird ein wenig seltsam; könnte es einfacher sein, die negativen Zahlen in ein separates Array Streifen aus, drehen das Zeichen, zu sortieren, dann umkehren. Sortieren Sie die positiven Zahlen, und dann schließlich die umgekehrte negative Zahlen kleben an der Vorderseite der positiven Nummern sortiert (die Zeichen wieder Spiegeln).

Answer 2

Dieses

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

ist ein Problem, weil bei der ersten Iteration, i Null ist und so pref[ 0 - 1 ] ist nicht sehr gut an der Arbeit gehen.

Ich habe nicht eine Referenz für radix praktisch sortiert, um zu bestimmen, was Sie sollte eigentlich hier tun.