JavaScript での基数ソート
-
26-09-2019 - |
質問
次のことを思いつきましたが、予想通り機能しません。
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?
}
解決
このループは基本的に同じことを、より 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];
}
}
C プログラマーのように行う代わりに、このループはリストのリスト (可能な 4 ビット値ごとに 1 つのリスト) を作成します。これは Javascript であるため、ビットシフト演算子は避けますが、ビットシフト演算子は使用します。 仕事, 、数値が大きくなると事態はおかしくなります。
コードは、「a」の各値の下位 4 ビットから開始して、「a」の要素を「パイル」の 1 つ (4 ビット値に対応するもの) の末尾にコピーします。次に、山を集めて、下位 4 ビットが 0、次に 1 であるすべての値から「a」を再構築します。(明らかにいくつかのギャップがあるため、それらはスキップされます。) ループ全体の各反復の終わりに、除数に基数が乗算され、次の 4 ビットのセットが検査されます。
除数が使用可能な整数の範囲を使い果たすと、完了です。
これは次の場合にのみ機能することに注意してください ポジティブ 数字。負の数でこれを行うと少し奇妙になります。負の数値を取り出して別の配列にし、符号を反転し、並べ替えてから逆順にする方が簡単かもしれません。正の数値を並べ替えてから、最後に反転した負の数値 (符号を再度反転) を並べ替えた正の数値の前に貼り付けます。
他のヒント
この
for(var i = 0; i < count.length; i++)
{
pref[i] = pref[i-1] + count[i-1];
}
最初の反復で、i
がゼロであるため、問題があるpref[ 0 - 1 ]
は非常によく仕事に行っていないので。
私はあなたが実際にここでやるべきかを決定する便利な基数ソートのための参照を持っていません。
所属していません StackOverflow