Radix Trier en JavaScript

Question

Je suis venu avec le suivant, mais cela ne fonctionne pas de manière prévisible.

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 essentiellement la même chose, d'une façon plus Javascript-y:

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 un programmeur C pourrait, cette boucle construit une liste de listes, une liste pour chaque possible Valeur 4 bits J'évite les opérateurs de décalage de bits parce que c'est Javascript et alors qu'ils font travaillent, les choses deviennent drôles quand les nombres deviennent grands. En commençant par les 4 bits les plus faibles de chaque valeur de "a", le code copie cet élément de "a" à la fin de l'une des "piles", c'est-à-dire celle correspondant à la valeur de 4 bits. Il rassemble ensuite les piles et reconstruit "a" à partir de toutes les valeurs dont les 4 bits bas étaient 0, puis 1, etc. (Clairement, il y aura des trous, donc ceux-ci sont ignorés.) A 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 sera examiné.

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

Notez que cela fonctionnera uniquement pour positifs 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é, de retourner le signe, de trier, puis de retourner. Trier les nombres positifs, puis enfin coller les nombres négatifs inversés (retournant les signes) à l'avant des nombres positifs triés. `A` contient le tableau d'entrée des entiers?

Answer 2

cette

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 de référence pour les tris radix pratiques pour déterminer ce que vous devriez faire ici.