Tri Radix en JavaScript

Question

J'ai trouvé ce qui suit, mais comme on pouvait s'y attendre, cela ne fonctionne pas.

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

Cette boucle fait fondamentalement la même chose, d'une manière plus 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];
  }
}

Au lieu de le faire comme le ferait un programmeur C, cette boucle crée une liste de listes, une liste pour chaque valeur possible de 4 bits.J'évite les opérateurs de décalage de bits car il s'agit de Javascript et pendant qu'ils le font travail, les choses deviennent drôles quand les nombres deviennent grands.

En commençant par les 4 bits faibles de chaque valeur de "a", le code copie cet élément de "a" à la fin de l'une des "piles", celle correspondant à la valeur de 4 bits.Il rassemble ensuite les piles et reconstruit "a" à partir de toutes les valeurs dont les 4 bits faibles étaient 0, puis 1, etc.(Il y aura clairement quelques lacunes, donc celles-ci sont ignorées.) À la fin de chaque itération de la boucle globale, le diviseur est multiplié par la base, de sorte que l'ensemble suivant de 4 bits soit examiné.

Une fois que le diviseur a épuisé la plage d’entiers disponible, c’est fait.

Notez que cela ne fonctionnera que pour positif Nombres.Faire cela avec des nombres négatifs devient un peu bizarre ;il pourrait être plus facile de supprimer les nombres négatifs dans un tableau séparé, d'inverser le signe, de trier, puis d'inverser.Triez les nombres positifs, puis collez enfin les nombres négatifs inversés (en retournant à nouveau les signes) devant les nombres positifs triés.

Answer 2

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

est un problème parce que la première itération, i est égal à zéro et ainsi pref[ 0 - 1 ] ne va pas fonctionner très bien.

Je n'ai pas une référence pour radix trie pratique pour déterminer ce que vous devriez effectivement faire ici.