Какой самый быстрый алгоритм сортировки для целых чисел 0-65535?

Question

Я должен отсортировать число целых чисел, которые могут иметь значения от 30 000 000 до 350 000 000. Там будет между 0 и 65.535 целых чисел, со средним счетом 20.000. Использование ОЗУ не имеет значения, важна только скорость.

Позже мне также придется разделить их на группы, причем деление всегда устанавливается, когда разрыв между двумя из этих значений составляет> 65,535, для чего и нужен алгоритм.

Если это имеет какое-либо значение, алгоритм будет использоваться в скрипте Perl.

Редактировать: Обдумав это и прочитав ответы, я кое-что понял: на самом деле меня не волнуют сами данные. Так как я действительно хочу найти начальные и конечные значения групп с небольшими пробелами, сортировка требует только создания сегментов и может отбрасывать данные.

Edit2: после некоторого тестирования и проверки предоставленных ответов, самый быстрый способ, который я нашел, был следующим:

my @sort = sort {$a <=> $b} @item_offsets;
my @buckets;
my $start = shift @sort;
push @buckets, [$start,$start];
for my $item ( @sort ) {
    if ( $item < $buckets[$#buckets][1]+$gap ) {
        $buckets[$#buckets][1] = $item;
    }
    else {
        push @buckets, [$item,$item];
    }
}
say $#buckets;

Answer 1

Я бы просто сделал массив блоков перед запуском алгоритма, по одному на каждую группу из 65536 последовательных значений. Контейнеры будут содержать минимальное и максимальное значения их содержимого, но сами не будут хранить содержимое. После запуска алгоритма выполните один проход по сегментам. Если есть два последовательных непустых сегмента с min (bucket2) -max (bucket1) <65536, объедините их. Объединение не произойдет, пока алгоритм не завершит работу. Откажитесь от любых пустых ведер. Этот алгоритм имеет линейное время. </p>

Обратите внимание на Сортировка ведер .

Answer 2

Маловероятно, что вы сможете написать алгоритм сортировки в Perl, который будет работать лучше, чем встроенная в Perl функция sort:

@numbers = sort {$a <=> $b} @numbers;

Вы можете поэкспериментировать с прагмой sort, чтобы увидеть, лучше ли конкретный алгоритм:

use sort '_quicksort';
use sort '_mergesort';

Поскольку ваши точки вырезания будут различаться в зависимости от распределения данных, я думаю, вам нужно сначала отсортировать весь список, а затем выполнить цикл по нему, чтобы выполнить вырезание.

my $prev  = shift @numbers;  # already sorted
my @group = [$prev];
my $i     = 0;

foreach my $n (@numbers) {
    $i++ if ($n - $prev > 65535);
    push @{$group[$i]}, $n;
    $prev = $n;
}

Answer 3

Я бы использовал сортировку по основанию, так как вам нужно сгруппировать вывод.

Answer 4

Я просто хотел сказать, что сортировка по основанию, http://en.wikipedia.org/wiki/Radix_sort однако это может быть немного выше того, что вы хотели реализовать, Introsort, как правило, является приемлемым решением для сортировки данных http://en.wikipedia.org/wiki/Introsort, это вариант быстрой сортировки, которая переключается на динамическую сортировку, когда она достигает меньших наборов, поскольку она быстрее на меньших наборах, чем быстрая сортировка.

Answer 5

Я бы попробовал это:

my @sorted = map { unpack "N" } sort map { pack "N" } @unsorted;

Answer 6

Если вы используете число в качестве индекса для массива, а затем увеличиваете счетчик этой позиции, вы «группируете» их и делаете это за один проход.

в псевдокоде:

while(morenumbers)
  sorted[[unsorted[number]]++
  number++

Если диапазон известен заранее, вы можете уменьшить индексирование значений (например, значение-30000, чтобы привести его в правильный диапазон).