В информатике целочисленная сортировка — это алгоритмическая проблема сортировки набора значений данных по целочисленным ключам. Алгоритмы, разработанные для целочисленной сортировки, также часто могут применяться к задачам сортировки, в которых ключами являются числа с плавающей точкой , рациональные числа или текстовые строки. [1] Возможность выполнять целочисленную арифметику над ключами позволяет алгоритмам целочисленной сортировки быть быстрее алгоритмов сортировки сравнения во многих случаях, в зависимости от деталей того, какие операции разрешены в модели вычислений, и насколько велики целые числа, подлежащие сортировке.
Алгоритмы сортировки целых чисел, включая сортировку Pigeonhole , сортировку подсчетом и сортировку по основанию, широко используются и практичны. Другие алгоритмы сортировки целых чисел с меньшими временными ограничениями в худшем случае не считаются практичными для компьютерных архитектур с 64 или менее битами на слово. Известно много таких алгоритмов, производительность которых зависит от комбинации количества сортируемых элементов, количества бит на ключ и количества бит на слово компьютера, выполняющего алгоритм сортировки.
Временные границы для алгоритмов сортировки целых чисел обычно зависят от трех параметров: количества n значений данных, которые необходимо отсортировать, величины K наибольшего возможного ключа, который необходимо отсортировать, и количества w бит, которые можно представить в одном машинном слове компьютера, на котором должен выполняться алгоритм. Обычно предполагается, что w ≥ log 2 (max( n , K ) ) ; то есть, что машинные слова достаточно велики, чтобы представлять индекс в последовательности входных данных, а также достаточно велики, чтобы представлять один ключ. [2]
Алгоритмы сортировки целых чисел обычно разрабатываются для работы в моделях вычислений с использованием машины указателей или машины с произвольным доступом . Основное различие между этими двумя моделями заключается в том, как может быть адресована память. Машина с произвольным доступом позволяет использовать любое значение, хранящееся в регистре, в качестве адреса операций чтения и записи памяти с удельной стоимостью за операцию. Эта возможность позволяет быстро реализовывать определенные сложные операции с данными с помощью табличного поиска. Напротив, в модели машины указателей операции чтения и записи используют адреса, хранящиеся в указателях, и не разрешается выполнять арифметические операции с этими указателями. В обеих моделях значения данных могут быть добавлены, а побитовые булевы операции и операции двоичного сдвига обычно также могут выполняться над ними за единицу времени за операцию. Однако различные алгоритмы сортировки целых чисел делают разные предположения о том, разрешено ли также умножение целых чисел как операция с единичным временем. [3] Также рассматривались другие более специализированные модели вычислений, такие как параллельная машина с произвольным доступом . [4]
Андерссон, Милтерсен и Торуп (1999) показали, что в некоторых случаях умножения или табличные поиски, требуемые некоторыми алгоритмами сортировки целых чисел, можно заменить настраиваемыми операциями, которые было бы проще реализовать на оборудовании, но которые обычно не доступны на компьютерах общего назначения. Торуп (2003) улучшил это, показав, как заменить эти специальные операции инструкциями по манипуляции битовыми полями , уже доступными на процессорах Pentium .
В моделях внешней памяти вычислений ни один известный алгоритм сортировки целых чисел не быстрее, чем сортировка сравнения. Исследователи показали, что в этих моделях ограниченные классы алгоритмов, которые ограничены в том, как они манипулируют своими ключами, не могут быть быстрее, чем сортировка сравнения, [5] и что алгоритм сортировки целых чисел, который быстрее, чем сортировка сравнения, будет подразумевать ложность стандартной гипотезы в сетевом кодировании . [6]
Очередь приоритетов — это структура данных для поддержания коллекции элементов с числовыми приоритетами, имеющая операции для поиска и удаления элемента с минимальным значением приоритета. Очереди приоритетов на основе сравнения, такие как двоичная куча, требуют логарифмического времени на обновление, но другие структуры, такие как дерево Ван Эмде Боаса или очередь ведров, могут быть быстрее для входных данных, приоритеты которых являются небольшими целыми числами. Эти структуры данных могут использоваться в алгоритме сортировки выбором , который сортирует коллекцию элементов, многократно находя и удаляя наименьший элемент из коллекции и возвращая элементы в порядке их нахождения. Очередь приоритетов может использоваться для поддержания коллекции элементов в этом алгоритме, и время для этого алгоритма для коллекции из n элементов может быть ограничено временем инициализации очереди приоритетов и последующего выполнения n операций поиска и удаления. Например, использование двоичной кучи в качестве очереди приоритетов в сортировке выбором приводит к алгоритму сортировки кучей , алгоритму сортировки сравнением, который занимает O ( n log n ) времени. Вместо этого использование сортировки выбором с очередью блоков дает форму сортировки методом «пигхон» , а использование деревьев Ван Эмде Боаса или других очередей с целочисленным приоритетом приводит к другим быстрым алгоритмам сортировки целых чисел. [7]
Вместо использования целочисленной приоритетной очереди в алгоритме сортировки можно пойти в другом направлении и использовать алгоритмы целочисленной сортировки как подпрограммы в структуре данных целочисленной приоритетной очереди. Торуп (2007) использовал эту идею, чтобы показать, что если возможно выполнить целочисленную сортировку за время T ( n ) на ключ, то то же самое ограничение по времени применяется к времени на операцию вставки или удаления в структуре данных приоритетной очереди. Редукция Торупа сложна и предполагает наличие либо быстрых операций умножения, либо табличных поисков, но он также предоставляет альтернативную приоритетную очередь, использующую только сложение и булевы операции со временем T ( n ) + T (log n ) + T (log log n ) + ... на операцию, максимум умножая время на итерированный логарифм . [7]
Классические алгоритмы сортировки целых чисел сортировка по пигмеям , сортировка подсчетом и поразрядная сортировка широко используются и практичны. [8] Большая часть последующих исследований алгоритмов сортировки целых чисел была сосредоточена не столько на практичности, сколько на теоретических улучшениях в их анализе наихудшего случая , и алгоритмы, которые приходят из этой линии исследований, не считаются практичными для современных 64-битных компьютерных архитектур, хотя эксперименты показали, что некоторые из этих методов могут быть улучшением поразрядной сортировки для данных с 128 или более битами на ключ. [9] Кроме того, для больших наборов данных почти случайные шаблоны доступа к памяти многих алгоритмов сортировки целых чисел могут мешать им по сравнению с алгоритмами сортировки сравнения, которые были разработаны с учетом иерархии памяти . [10]
Сортировка целых чисел является одним из шести тестов в наборе тестов дискретной математики высокопроизводительных вычислительных систем DARPA [11] и одним из одиннадцати тестов в наборе параллельных тестов NAS .
Сортировка Pigeonhole или сортировка подсчетом могут сортировать n элементов данных с ключами в диапазоне от 0 до K − 1 за время O ( n + K ) . В сортировке Pigeonhole (часто называемой сортировкой по контейнерам) указатели на элементы данных распределяются по таблице контейнеров, представленных в виде типов данных коллекции , таких как связанные списки , с использованием ключей в качестве индексов в таблице. Затем все контейнеры объединяются вместе для формирования выходного списка. [12] Сортировка подсчетом использует таблицу счетчиков вместо таблицы контейнеров для определения количества элементов с каждым ключом. Затем вычисление суммы префикса используется для определения диапазона позиций в отсортированном выводе, в которые должны быть помещены значения с каждым ключом. Наконец, во втором проходе по входу каждый элемент перемещается в позицию своего ключа в выходном массиве. [13] Оба алгоритма включают в себя только простые циклы по входным данным (занимающим время O ( n ) ) и по набору возможных ключей (занимающим время O ( K ) ), что дает их общее ограничение по времени O ( n + K ) .
Сортировка по радиксу — это алгоритм сортировки, который работает для ключей большего размера, чем сортировка по принципу «пиг-хол» или сортировка подсчетом, выполняя несколько проходов по данным. Каждый проход сортирует входные данные, используя только часть ключей, используя другой алгоритм сортировки (например, сортировка по принципу «пиг-хол» или сортировка подсчетом), который подходит только для ключей небольшого размера. Чтобы разбить ключи на части, алгоритм сортировки по радиксу вычисляет позиционную нотацию для каждого ключа в соответствии с некоторым выбранным основанием ; затем часть ключа, используемая для i- го прохода алгоритма, является i- й цифрой в позиционной нотации для полного ключа, начиная с наименее значимой цифры и продвигаясь к наиболее значимой. Чтобы этот алгоритм работал правильно, алгоритм сортировки, используемый в каждом проходе по данным, должен быть стабильным : элементы с одинаковыми цифрами не должны меняться позициями друг с другом. Для наибольшей эффективности основание должно быть выбрано таким образом, чтобы оно было близко к числу элементов данных n . Кроме того, использование степени двойки около n в качестве основания позволяет быстро вычислять ключи для каждого прохода, используя только быстрые операции бинарного сдвига и маски. С этими вариантами и с сортировкой Pigeonhole или сортировкой подсчета в качестве базового алгоритма, алгоритм сортировки radix может сортировать n элементов данных с ключами в диапазоне от 0 до K − 1 за время O ( n log n K ) . [14]
Было разработано много алгоритмов сортировки целых чисел, теоретический анализ которых показывает, что они ведут себя лучше, чем сортировка сравнением, сортировка по принципу «ящик» или сортировка по радиксу для достаточно больших комбинаций параметров, определяющих количество сортируемых элементов, диапазон ключей и размер машинного слова. Какой алгоритм имеет лучшую производительность, зависит от значений этих параметров. Однако, несмотря на их теоретические преимущества, эти алгоритмы не являются улучшением для типичных диапазонов этих параметров, которые возникают в практических задачах сортировки. [9]
Дерево Ван Эмде Боаса может использоваться в качестве очереди с приоритетами для сортировки набора из n ключей, каждый из которых находится в диапазоне от 0 до K − 1 , за время O ( n log log K ) . Это теоретическое улучшение по сравнению с сортировкой по основанию, когда K достаточно велико. Однако для использования дерева Ван Эмде Боаса либо нужна напрямую адресуемая память из K слов, либо нужно смоделировать ее с помощью хэш-таблицы , сокращая пространство до линейного, но делая алгоритм рандомизированным. Другая очередь с приоритетами с похожей производительностью (включая необходимость рандомизации в виде хэш-таблиц) — это Y-fast trie Уилларда (1983).
Более сложная техника с похожим вкусом и с лучшей теоретической производительностью была разработана Киркпатриком и Райшем (1984). Они заметили, что каждый проход радиксной сортировки можно интерпретировать как технику сокращения диапазона, которая за линейное время уменьшает максимальный размер ключа в n раз ; вместо этого их техника уменьшает размер ключа до квадратного корня его предыдущего значения (уменьшая вдвое количество бит, необходимых для представления ключа), снова за линейное время. Как и в радиксной сортировке, они интерпретируют ключи как двузначные числа с основанием b для основания b, которое приблизительно равно √ K. Затем они группируют элементы, которые должны быть отсортированы, в блоки в соответствии с их высокими цифрами за линейное время, используя либо большую, но неинициализированную память с прямой адресацией, либо хэш-таблицу. У каждого блока есть представитель, элемент в блоке с самым большим ключом; затем они сортируют список элементов, используя в качестве ключей высокие цифры для представителей и низкие цифры для непредставителей. Группируя элементы из этого списка снова в блоки, каждый блок может быть помещен в отсортированный порядок, и путем извлечения представителей из отсортированного списка блоки могут быть объединены вместе в отсортированный порядок. Таким образом, за линейное время задача сортировки сводится к другой рекурсивной задаче сортировки, в которой ключи намного меньше, квадратный корень их предыдущей величины. Повторение этого уменьшения диапазона до тех пор, пока ключи не станут достаточно маленькими для сортировки по блокам, приводит к алгоритму со временем выполнения O( n log log n K ) .
Сложный рандомизированный алгоритм Хана и Торупа (2002) в модели вычислений Word RAM позволяет сократить эти временные ограничения еще больше, до O( n √ log log K ) .
Алгоритм сортировки целых чисел называется неконсервативным , если он требует размер слова w , который значительно больше, чем log max( n , K ) . [15] В качестве крайнего примера, если w ≥ K , и все ключи различны, то набор ключей можно отсортировать за линейное время, представив его в виде битового вектора с битом 1 в позиции i , когда i является одним из входных ключей, а затем многократно удаляя наименее значимый бит. [16]
Неконсервативный алгоритм упакованной сортировки Альберса и Хагерупа (1997) использует подпрограмму, основанную на битонной сортировочной сети Кена Батчера , для слияния двух отсортированных последовательностей ключей, каждая из которых достаточно коротка, чтобы быть упакованной в одно машинное слово. Входные данные для алгоритма упакованной сортировки, последовательность элементов, хранящихся по одному на слово, преобразуются в упакованную форму, последовательность слов, каждое из которых содержит несколько элементов в отсортированном порядке, путем многократного использования этой подпрограммы для удвоения количества элементов, упакованных в каждое слово. Как только последовательность находится в упакованной форме, Альберс и Хагерупа используют форму сортировки слиянием для ее сортировки; когда две последовательности объединяются для формирования одной более длинной последовательности, ту же самую подпрограмму битонной сортировки можно использовать для многократного извлечения упакованных слов, состоящих из наименьших оставшихся элементов двух последовательностей. Этот алгоритм получает достаточное ускорение от своего упакованного представления, чтобы сортировать свои входные данные за линейное время, когда возможно, чтобы одно слово содержало Ω(log n log log n ) ключей; то есть, когда log K log n log log n ≤ cw для некоторой константы c > 0 .
Сортировка Pigeonhole, сортировка подсчетом, сортировка по радиксу и сортировка по дереву Ван Эмде Боаса работают лучше всего, когда размер ключа невелик; для достаточно больших ключей они становятся медленнее, чем алгоритмы сортировки сравнением. Однако, когда размер ключа или размер слова очень велик относительно количества элементов (или, что эквивалентно, когда количество элементов невелико), может снова стать возможным выполнять быструю сортировку, используя различные алгоритмы, которые используют преимущества параллелизма, присущего возможности выполнять арифметические операции над большими словами.
Ранний результат в этом направлении был получен Ajtai, Fredman & Komlós (1984) с использованием модели вычислений cell-probe (искусственная модель, в которой сложность алгоритма измеряется только количеством обращений к памяти, которые он выполняет). Основываясь на своей работе, Fredman & Willard (1994) описали две структуры данных, Q-heap и atomic heap, которые можно реализовать на машине с произвольным доступом. Q-heap является бит-параллельной версией двоичного trie и позволяет выполнять как операции очереди приоритетов, так и запросы последователей и предшественников за постоянное время для наборов из O ((log N ) 1/4 ) элементов, где N ≤ 2 w — размер предварительно вычисленных таблиц, необходимых для реализации структуры данных. Атомная куча — это B-дерево , в котором каждый узел дерева представлен как Q-heap; она позволяет выполнять операции очереди приоритетов за постоянное время (и, следовательно, сортировку) для наборов из (log N ) O (1) элементов.
Андерссон и др. (1998) предлагают рандомизированный алгоритм, называемый сортировкой по сигнатуре, который позволяет сортировать наборы из до 2 O ((log w ) 1/2 − ε ) элементов за раз за линейное время для любой константы ε > 0 . Как и в алгоритме Киркпатрика и Райша, они выполняют сокращение диапазона, используя представление ключей в виде чисел в базе b для тщательного выбора b . Их алгоритм сокращения диапазона заменяет каждую цифру сигнатурой, которая представляет собой хешированное значение с O (log n ) битами, так что разные значения цифр имеют разные сигнатуры. Если n достаточно мало, числа, сформированные в результате этого процесса замены, будут значительно меньше исходных ключей, что позволяет неконсервативному алгоритму упакованной сортировки Альберса и Хагерупа (1997) сортировать замененные числа за линейное время. Из отсортированного списка замененных чисел можно сформировать сжатое дерево ключей за линейное время, а дочерние элементы каждого узла в дереве можно отсортировать рекурсивно, используя только ключи размера b , после чего обход дерева даст отсортированный порядок элементов.
Фредман и Уиллард (1993) представили трансдихотомическую модель анализа для алгоритмов сортировки целых чисел, в которой ничего не предполагается о диапазоне целочисленных ключей, и производительность алгоритма должна быть ограничена функцией только количества значений данных. В качестве альтернативы, в этой модели время выполнения алгоритма для набора из n элементов предполагается худшим случаем времени выполнения для любой возможной комбинации значений K и w . Первым алгоритмом этого типа был алгоритм сортировки дерева слияния Фредмана и Уилларда , который выполняется за время O( n log n / log log n ) ; это улучшение по сравнению со сортировкой сравнением для любого выбора K и w . Альтернативная версия их алгоритма, которая включает использование случайных чисел и операций целочисленного деления, улучшает это до O( n √ log n ) .
С тех пор, как они работали, были разработаны еще лучшие алгоритмы. Например, многократно применяя технику сокращения диапазона Киркпатрика-Райша до тех пор, пока ключи не станут достаточно маленькими для применения алгоритма упакованной сортировки Альберса-Хагерупа, можно выполнить сортировку за время O ( n log log n ) ; однако часть сокращения диапазона этого алгоритма требует либо большой памяти (пропорциональной √ K ), либо рандомизации в форме хэш-таблиц. [17]
Han & Thorup (2002) показали, как сортировать за рандомизированное время O( n √ log log n ) . Их техника включает в себя использование идей, связанных с сортировкой сигнатуры, для разбиения данных на множество небольших подсписков, достаточно малого размера, чтобы сортировка сигнатуры могла эффективно сортировать каждый из них. Также возможно использовать похожие идеи для сортировки целых чисел детерминированно за время O ( n log log n ) и линейное пространство. [18] Используя только простые арифметические операции (без умножений или поиска в таблице), можно сортировать за рандомизированное ожидаемое время O ( n log log n ) [19] или детерминированно за время O ( n (log log n ) 1 + ε ) для любой константы ε > 0 . [1]