Целочисленная сортировка

Целочисленная сортировка — задача сортировки некоторого набора значений при помощи целочисленных ключей. Алгоритмы целочисленной сортировки можно применять и для задач, в которых ключами являются числа с плавающей запятой или текстовые строки. Возможность выполнения целочисленных арифметических операций над ключами позволяет алгоритмам целочисленной сортировки быть во многих случаях быстрее, чем аналогичные алгоритмы сортировки с использованием сравнений, в зависимости от допустимых в модели вычислений операций и величины чисел-ключей.

Обычные алгоритмы целочисленной сортировки: корзинная сортировка, поразрядная сортировка, сортировка подсчётом широко распространены и эффективны. Дальнейшие исследования алгоритмов целочисленной сортировки были направлены на теоретические улучшения худшего случая, а алгоритмы, которые были получены, не считаются эффективными для современных 64-битных компьютеров, хотя эксперименты показали, что некоторые из этих методов могут быть лучше поразрядной сортировки данных со 128 и более битами на ключ. Кроме того, для больших наборов данных почти произвольный характер доступа к памяти алгоритмов целочисленной сортировки является ограничением, особенно в сравнении с другими алгоритмами сортировок, которые были разработаны с учётом иерархичной структуры памяти.

Целочисленная сортировка используется в одном из шести эталонных тестов в наборе DARPA High Productivity Computing Systems Discrete Mathematics и в одном из одиннадцати критериев NAS Parallel Benchmarks suite.

Модели вычислений

Временные ограничения алгоритмов целочисленной сортировки обычно зависят от трех параметров: n {displaystyle n} — количество значений данных, которые должны быть отсортированы, K {displaystyle K} — порядок величины максимально возможного ключа и W {displaystyle W} — число бит в машинном слове компьютера, на котором алгоритм будет выполняться. Как правило, полагается, что W ⩾ log 2 ⁡ max ( n , K ) {displaystyle Wgeqslant log _{2}max(n,K)} , то есть, машинные слова достаточно большие, чтобы представлять как индекс в последовательности входных данных, так и ключ.

Алгоритмы целочисленной сортировки, как правило, разрабатываются для работы либо для машины указателей, либо для машины с произвольным доступом к памяти. Основное различие этих моделей заключается в том, что машины с произвольным доступом позволяют использовать произвольное значение в регистре в качестве адреса памяти в операциях чтения и записи с единичной временной стоимостью, а сложные манипуляции с данными организовать с помощью таблицы поиска. Модель машины указателей позволяет доступ к памяти только через указатели, которыми нельзя манипулировать путём арифметических операций. В обеих моделях побитовые операции могут быть выполнены, как правило, за один квант времени. Различные алгоритмы целочисленной сортировки делают разные предположения о том, можно ли выполнять целочисленное умножение за один квант времени. Могут рассматриваться и более специализированные модели вычислений, такие как параллельные машины с произвольным доступом.

В 1999 году показано, что в некоторых случаях умножение или табличный поиск, необходимый для некоторых алгоритмов целочисленной сортировки, можно заменить на специализированные операции, которые могут быть легко реализованы аппаратными средствами, но обычно недоступны на компьютерах общего назначения.