فرز Radix في 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?
}
المحلول
هذه الحلقة تفعل نفس الشيء بشكل أساسي ، بطريقة أكثر جافا سكريبت:
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 بت. أتجنب مشغلو البتات لأن هذا هو JavaScript وبينما يفعلون ذلك الشغل, ، تصبح الأمور مضحكة عندما تصبح الأرقام كبيرة.
بدءًا من 4 بتات منخفضة من كل قيمة في "A" ، يقوم الكود بنسخ عنصر "A" إلى نهاية أحد "الأكوام" ، وهو ما يتوافق مع القيمة 4 بت. ثم يجمع الأكوام ويعيد البناء "A" بدءًا من جميع القيم التي كانت 4 بتات منخفضة 0 ، ثم 1 ، وما إلى ذلك (من الواضح أن هناك بعض الثغرات ، لذلك يتم تخطيها.) في نهاية كل تكرار من الحلقة الكلية ، يتم ضرب المقسوم بواسطة Radix ، بحيث يتم فحص المجموعة التالية من 4 بت.
بمجرد أن يستنفد المقسوم النطاق المتاح من الأعداد الصحيحة ، يتم ذلك.
لاحظ أن هذا سيعمل فقط إيجابي أعداد. القيام بذلك مع الأرقام السلبية يصبح غريبا بعض الشيء. قد يكون من الأسهل تجريد الأرقام السلبية في صفيف منفصل ، اقلب العلامة ، الفرز ، ثم عكس. قم بفرز الأرقام الإيجابية ، ثم قم أخيرًا بصق الأرقام السالبة المعكوسة (تقلب العلامات مرة أخرى) إلى مقدمة الأرقام الإيجابية المرتبة.
نصائح أخرى
هذه
for(var i = 0; i < count.length; i++)
{
pref[i] = pref[i-1] + count[i-1];
}
هي مشكلة لأن التكرار الأول ، i
هو الصفر وهكذا pref[ 0 - 1 ]
لن يعمل بشكل جيد للغاية.
ليس لدي مرجع لأنواع Radix في متناول يدي لتحديد ما يجب أن تفعله بالفعل هنا.