Radix Сортировка в JavaScript - PullRequest
Новая
       4

Radix Сортировка в JavaScript

3 голосов
/ 29 сентября 2010

Я придумал следующее, но, как и ожидалось, оно не работает. 

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?
}

Ответы [ 2 ]

6 голосов
/ 29 сентября 2010

Этот цикл в основном делает то же самое, более в 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];
  }
}

Вместо того, чтобы делать это так, как мог бы программист на С, этот цикл создает список списков, по одному списку для каждого.возможное 4-битное значение.Я избегаю операторов сдвига битов, потому что это Javascript, и хотя они работают , все становится смешным, когда числа становятся большими.

Начиная с младших 4 битов каждого значения в «а»,код копирует этот элемент «a» в конец одной из «груд», которая соответствует 4-битному значению.Затем он собирает груды и восстанавливает «a», начиная со всех значений, младшие 4 бита которых были 0, затем 1 и т. Д. (Ясно, что будут некоторые пробелы, поэтому они пропускаются.) В конце каждой итерацииделения общего цикла делитель умножается на основание, так что будет рассмотрен следующий набор из 4 битов.

Как только делитель исчерпал доступный диапазон целых чисел, это делается.

Обратите внимание, что это будет работать только для положительных чисел.Делать это с отрицательными числами становится немного странно;может быть проще выделить отрицательные числа в отдельный массив, перевернуть знак, отсортировать, а затем развернуть.Сортируйте положительные числа, а затем, наконец, приклейте обратные отрицательные числа (снова переворачивая знаки) в начало отсортированных положительных чисел.

0 голосов
/ 29 сентября 2010

это 

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

является проблемой, потому что на первой итерации i равно нулю, и поэтому pref[ 0 - 1 ] не будет работать очень хорошо.

У меня нет справки по радикальным сортам, чтобы определить, что вам действительно следует делать здесь.

...