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

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

Целочисленные алгоритмы сортировки, включая голубятня сортировка, счетная сортировка, и радиальная сортировка широко используются и практичны. Другие алгоритмы целочисленной сортировки с меньшими временными границами для наихудшего случая не подходят для компьютерных архитектур с 64 или менее битами на слово. Известно много таких алгоритмов, производительность которых зависит от комбинации количества элементов, которые нужно отсортировать, количества бит на ключ и количества бит на слово компьютера, выполняющего алгоритм сортировки.

Общие Соображения

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

Границы времени для алгоритмов целочисленной сортировки обычно зависят от трех параметров: числа п значений данных для сортировки, величина K максимально возможного ключа для сортировки, и число ш битов, которые могут быть представлены в одном машинном слове компьютера, на котором должен выполняться алгоритм. Обычно предполагается, что ш ≥ журнал2(Максимум(п, K)); то есть машинные слова достаточно велики, чтобы представлять индекс в последовательности входных данных, а также достаточно велики, чтобы представлять единственный ключ.[2]

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

Андерссон, Милтерсен и Торуп (1999) показали, что в некоторых случаях умножения или поиск в таблицах, требуемые некоторыми алгоритмами целочисленной сортировки, можно заменить настраиваемыми операциями, которые легче реализовать на аппаратном уровне, но которые обычно недоступны на компьютерах общего назначения. Thorup (2003) улучшил это, показав, как заменить эти специальные операции на битовое поле инструкции по манипуляции уже доступны на Pentium процессоры.

В модели внешней памяти вычислений, нет известного алгоритма целочисленной сортировки быстрее, чем сортировка сравнения. Исследователи показали, что в этих моделях ограниченные классы алгоритмов, которые ограничены в том, как они манипулируют своими ключами, не могут быть быстрее, чем сортировка сравнения,[5] и что алгоритм целочисленной сортировки, который быстрее, чем сортировка сравнения, будет означать ложность стандартной гипотезы в сетевое кодирование.[6]

Сортировка по сравнению с очередями с целочисленным приоритетом

А приоритетная очередь представляет собой структуру данных для поддержки коллекции элементов с числовыми приоритетами, имеющую операции для поиска и удаления элемента с минимальным значением приоритета. Очереди приоритетов на основе сравнения, такие как двоичная куча принимать логарифмическое время на обновление, но другие структуры, такие как дерево ван Эмде Боас или же очередь ведра может быть быстрее для входов, чьи приоритеты - небольшие целые числа. Эти структуры данных можно использовать в сортировка выбора алгоритм, который сортирует коллекцию элементов, многократно находя и удаляя наименьший элемент из коллекции, и возвращая элементы в том порядке, в котором они были найдены. Очередь с приоритетами может использоваться для поддержки коллекции элементов в этом алгоритме, а время для этого алгоритма в коллекции п элементы могут быть ограничены временем для инициализации очереди с приоритетом, а затем для выполнения п найти и удалить операции. Например, используя двоичная куча поскольку приоритетная очередь в сортировке выбора приводит к куча сортировки алгоритм, алгоритм сортировки сравнения, который принимает О(п бревно п) время. Вместо этого использование сортировки по выбору с очередью ведра дает форму голубятня сортировка, а использование деревьев Ван Эмде Боаса или других очередей с целочисленным приоритетом приводит к другим алгоритмам быстрой целочисленной сортировки.[7]

Вместо использования очереди с целочисленным приоритетом в алгоритме сортировки можно пойти в другом направлении и использовать алгоритмы целочисленной сортировки в качестве подпрограмм в структуре данных очереди с целочисленным приоритетом. Thorup (2007) использовал эту идею, чтобы показать, что, если возможно выполнить целочисленную сортировку во времени Т(п) на ключ, то такая же временная привязка применяется ко времени каждой операции вставки или удаления в структуре данных очереди приоритетов. Редукция Торупа сложна и предполагает наличие либо операций быстрого умножения, либо поиска в таблице, но он также предоставляет альтернативную очередь с приоритетом, используя только сложение и логические операции со временем. Т(п) + Т(бревно п) + Т(журнал журнал п) + ... за операцию, самое большее умножение времени на повторный логарифм.[7]

Удобство использования

Классические алгоритмы целочисленной сортировки голубятня сортировка, счетная сортировка, и радиальная сортировка широко используются и практичны.[8] Большая часть последующих исследований алгоритмов целочисленной сортировки была сосредоточена не столько на практичности, сколько на теоретических улучшениях их анализ наихудшего случая, и алгоритмы, полученные в результате этого исследования, не считаются практичными для текущих 64-битный компьютерные архитектуры, хотя эксперименты показали, что некоторые из этих методов могут быть улучшением сортировки по основанию для данных со 128 или более битами на ключ.[9] Кроме того, для больших наборов данных почти случайное шаблоны доступа к памяти многих целочисленных алгоритмов сортировки могут затруднить их по сравнению с алгоритмами сортировки сравнения, которые были разработаны с иерархия памяти в уме.[10]

Целочисленная сортировка обеспечивает одно из шести ориентиры в DARPA Вычислительные системы высокой производительности Набор тестов по дискретной математике,[11] и один из одиннадцати тестов в Параллельные тесты NAS люкс.

Практические алгоритмы

Сорт голубятни или же счетная сортировка могут оба сортировать п элементы данных, имеющие ключи в диапазоне от 0 к K − 1 во время О(п + K). В голубятня сортировка (часто называемая сортировкой по сегментам) указатели на элементы данных распределяются по таблице сегментов, представленной как коллекция типы данных, такие как связанные списки, используя ключи как индексы в таблице. Затем все сегменты объединяются вместе, чтобы сформировать выходной список.[12] Сортировка подсчета использует таблицу счетчиков вместо таблицы сегментов, чтобы определить количество элементов с каждым ключом. Затем сумма префикса вычисление используется для определения диапазона позиций в отсортированном выводе, в который должны быть помещены значения с каждым ключом. Наконец, при втором проходе по входу каждый элемент перемещается в позицию своего ключа в выходном массиве.[13] Оба алгоритма включают только простые циклы по входным данным (требующие времени О(п)) и по набору возможных ключей (требуется время О(K)), отдавая свои О(п + K) общий срок.

Radix sort - это алгоритм сортировки, который работает для ключей большего размера, чем сортировка по ячейкам или сортировка с подсчетом, путем выполнения нескольких проходов по данным. Каждый проход сортирует ввод, используя только часть ключей, используя другой алгоритм сортировки (например, сортировку по ячейкам или подсчет), который подходит только для маленьких ключей. Чтобы разбить ключи на части, алгоритм поразрядной сортировки вычисляет позиционная запись для каждого ключа, по некоторым выбранным основание; затем часть ключа, используемая для я-й проход алгоритма - это я-я цифра в позиционном обозначении полного ключа, начиная с наименее значащей цифры и переходя к наиболее значимой. Чтобы этот алгоритм работал правильно, алгоритм сортировки, используемый при каждом проходе по данным, должен быть стабильный: элементы с одинаковыми цифрами не должны меняться друг с другом. Для наибольшей эффективности следует выбирать систему счисления, близкую к количеству элементов данных, п. Кроме того, используя сила двух возле п поскольку основание системы счисления позволяет быстро вычислять ключи для каждого прохода, используя только операции быстрого двоичного сдвига и маски. С помощью этих вариантов, а также с помощью сортировки по ячейкам или сортировки с подсчетом в качестве базового алгоритма, алгоритм сортировки по основанию может выполнять сортировку п элементы данных с ключами в диапазоне от 0 к K − 1 во время О(п бревноп K).[14]

Теоретические алгоритмы

Было разработано множество алгоритмов целочисленной сортировки, теоретический анализ которых показывает, что они работают лучше, чем сортировка сравнения, сортировка по ячейкам или сортировка по основанию для достаточно больших комбинаций параметров, определяющих количество элементов для сортировки, диапазон ключей и размер машинного слова. Алгоритм имеет лучшую производительность в зависимости от значений этих параметров. Однако, несмотря на их теоретические преимущества, эти алгоритмы не являются улучшением для типичных диапазонов этих параметров, которые возникают в практических задачах сортировки.[9]

Алгоритмы для маленьких ключей

А Дерево Ван Эмде Боаса может использоваться как приоритетная очередь для сортировки набора п ключи, каждый в диапазоне от 0 к K − 1, во время О(п журнал журнал K). Это теоретическое улучшение по сравнению с сортировкой по основанию, когда K достаточно большой. Однако, чтобы использовать дерево Ван Эмде Боаса, требуется либо непосредственно адресуемая память K слова, или нужно смоделировать это с помощью хеш-таблица, уменьшая пространство до линейного, но делая алгоритм рандомизированным. Другой приоритетной очередью с аналогичной производительностью (включая необходимость рандомизации в виде хеш-таблиц) является Y-fast trie из Уиллард (1983).

Более сложная техника с аналогичным вкусом и лучшими теоретическими характеристиками была разработана Киркпатрик и Райш (1984). Они заметили, что каждый проход поразрядной сортировки можно интерпретировать как метод уменьшения диапазона, который за линейное время уменьшает максимальный размер ключа в несколько раз.п; вместо этого их метод уменьшает размер ключа до квадратного корня из его предыдущего значения (уменьшая вдвое количество битов, необходимых для представления ключа), снова за линейное время. Как и в случае сортировки по основанию, они интерпретируют ключи как двузначное основание -б числа для базы б это примерно √K. Затем они группируют элементы, которые нужно отсортировать, в сегменты в соответствии с их старшими цифрами за линейное время, используя либо большую, но неинициализированную память с прямым адресом, либо хеш-таблицу. У каждого ведра есть представитель, предмет в ведре с самым большим ключом; Затем они сортируют список элементов, используя в качестве ключей старшие цифры для представителей и младшие цифры для не-представителей. Снова группируя элементы из этого списка в сегменты, каждый сегмент может быть размещен в отсортированном порядке, и путем извлечения представителей из отсортированного списка сегменты могут быть объединены вместе в отсортированный порядок. Таким образом, в линейном времени проблема сортировки сводится к другой задаче рекурсивной сортировки, в которой ключи намного меньше, квадратный корень из их предыдущей величины. Повторение этого уменьшения диапазона до тех пор, пока ключи не станут достаточно маленькими для сортировки по сегментам, приводит к алгоритму с временем выполнения O (п журнал журналп K).

Сложный рандомизированный алгоритм Хан и Торуп (2002) в слово RAM модель вычисления позволяет сократить эти временные рамки еще больше, до O (п√журнал журнал K).

Алгоритмы для больших слов

Алгоритм целочисленной сортировки называется неконсервативный если требуется размер слова ш что значительно больше, чем журнал макс (п, K).[15] В крайнем случае, если ш ≥ K, и все ключи различны, то набор ключей можно отсортировать за линейное время, представив его как битвектор, с 1 битом в позиции я когда я является одним из ключей ввода, а затем многократно удаляет младший бит.[16]

Неконсервативный алгоритм упакованной сортировки Альберс и Хагеруп (1997) использует подпрограмму, основанную на Кен Батчер с битонная сортировочная сеть, за слияние две отсортированные последовательности ключей, каждая из которых достаточно коротка, чтобы их можно было поместить в одно машинное слово. Вход в алгоритм упакованной сортировки, последовательность элементов, хранящихся по одному на слово, преобразуется в упакованную форму, последовательность слов, каждое из которых содержит несколько элементов в отсортированном порядке, с помощью этой подпрограммы многократно, чтобы удвоить количество элементов, упакованных в каждую. слово. Когда последовательность упакована, Альберс и Хагеруп используют форму Сортировка слиянием отсортировать его; когда две последовательности объединяются в одну более длинную последовательность, одна и та же подпрограмма битонной сортировки может использоваться для многократного извлечения упакованных слов, состоящих из наименьших оставшихся элементов двух последовательностей. Этот алгоритм получает достаточное ускорение от своего упакованного представления, чтобы сортировать его ввод за линейное время всякий раз, когда возможно, чтобы одно слово содержало Ω (журнал п журнал журнал п) ключи; то есть когда бревно K бревно п журнал журнал п ≤ cw для некоторой постоянной c > 0.

Алгоритмы для нескольких предметов

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

Ранний результат в этом направлении был получен Айтай, Фредман и Комлос (1984) с использованием модель клетки-зонда вычислений (искусственная модель, в которой сложность алгоритма измеряется только количеством обращений к памяти, которые он выполняет). Опираясь на их работу, Фредман и Уиллард (1994) описаны две структуры данных, Q-куча и атомарная куча, которые могут быть реализованы на машине с произвольным доступом. Q-heap - это бит-параллельная версия двоичного файла. три, и позволяет выполнять как приоритетные операции очереди, так и запросы преемников и предшественников в постоянное время для наборов О((бревно N)1/4) предметы, где N ≤ 2ш - это размер предварительно вычисленных таблиц, необходимых для реализации структуры данных. Атомная куча - это B-дерево в котором каждый узел дерева представлен как Q-куча; он позволяет выполнять операции очереди с постоянным приоритетом времени (и, следовательно, сортировку) для наборов (бревно N)О(1) Предметы.

Андерссон и др. (1998) предоставить рандомизированный алгоритм, называемый сортировкой по сигнатуре, который позволяет выполнять линейную сортировку по времени наборов до 2О((бревно ш)1/2 - ε) элементов за раз, для любой постоянной ε> 0. Как и в алгоритме Киркпатрика и Райша, они выполняют сокращение диапазона, используя представление ключей в виде чисел в базеб для тщательного выбора б. Их алгоритм уменьшения диапазона заменяет каждую цифру подписью, которая представляет собой хешированное значение с О(бревно п) такие биты, что разные цифровые значения имеют разные подписи. Если п достаточно мало, числа, сформированные этим процессом замены, будут значительно меньше, чем исходные ключи, что позволяет использовать неконсервативный алгоритм упакованной сортировки Альберс и Хагеруп (1997) отсортировать замененные числа за линейное время. Из отсортированного списка заменяемых номеров можно сформировать сжатый три ключей за линейное время, а потомки каждого узла в дереве могут быть отсортированы рекурсивно, используя только ключи размера б, после чего обход дерева производит отсортированный порядок элементов.

Транс-дихотомические алгоритмы

Фредман и Уиллард (1993) представил трансдихотомическая модель анализа целочисленных алгоритмов сортировки, в которых ничего не предполагается о диапазоне целочисленных ключей, и нужно ограничивать производительность алгоритма только функцией количества значений данных. В качестве альтернативы в этой модели время работы алгоритма на множестве п предметы предполагается худший случай время работы при любой возможной комбинации значений K иш. Первым алгоритмом этого типа был алгоритм Фредмана и Уилларда. дерево слияния алгоритм сортировки, работающий во времени O (п бревно п / журнал журнал п); это улучшение по сравнению со сравнительной сортировкой для любого выбора K иш. Альтернативная версия их алгоритма, которая включает использование случайных чисел и операций целочисленного деления, улучшает это до O (п√бревно п).

С момента их работы были разработаны даже лучшие алгоритмы. Например, многократно применяя технику сокращения диапазона Киркпатрика – Райша до тех пор, пока ключи не станут достаточно маленькими для применения алгоритма упакованной сортировки Альберса – Хагерапа, можно выполнить сортировку по времени О(п журнал журнал п); однако часть этого алгоритма для уменьшения диапазона требует либо большой памяти (пропорциональной √K) или рандомизация в виде хеш-таблиц.[17]

Хан и Торуп (2002) показал, как сортировать в случайное время O (п√журнал журнал п). Их методика включает использование идей, связанных с сортировкой сигнатур, для разделения данных на множество небольших подсписок, размер которых достаточно мал, чтобы сортировка сигнатур могла эффективно сортировать каждый из них. Также можно использовать аналогичные идеи для детерминированной сортировки целых чисел по времени. О(п журнал журнал п) и линейное пространство.[18] Используя только простые арифметические операции (без умножения или поиска в таблице), можно сортировать в случайное ожидаемое время О(п журнал журнал п)[19] или детерминированно по времени О(п (журнал журнал п)1 + ε) для любой постоянной ε> 0.[1]

Рекомендации

Сноски
  1. ^ а б Хан и Торуп (2002).
  2. ^ Фредман и Уиллард (1993).
  3. ^ Вопрос о том, должны ли быть разрешены операции целочисленного умножения или поиска в таблице, восходит к Фредман и Уиллард (1993); смотрите также Андерссон, Милтерсен и Торуп (1999).
  4. ^ Рейф (1985); комментарий в Коул и Вишкин (1986); Хагеруп (1987); Bhatt et al. (1991); Альберс и Хагеруп (1997).
  5. ^ Аггарвал и Виттер (1988).
  6. ^ Farhadi et al. (2020).
  7. ^ а б Чоудхури (2008).
  8. ^ Макилрой, Бостик и Макилрой (1993); Андерссон и Нильссон (1998).
  9. ^ а б Рахман и Раман (1998).
  10. ^ Педерсен (1999).
  11. ^ Тесты дискретной математики DARPA HPCS, Дункан А. Буэлл, Университет Южной Каролины, получено 20 апреля 2011 г.
  12. ^ Гудрич и Тамассия (2002). Несмотря на то что Cormen et al. (2001) также описывают версию этого алгоритма сортировки, версия, которую они описывают, адаптирована для входных данных, где ключи являются действительными числами с известным распределением, а не для целочисленной сортировки.
  13. ^ Cormen et al. (2001), 8.2 Сортировка подсчета, стр. 168–169.
  14. ^ Комри (1929–1930); Cormen et al. (2001), 8.3 Radix Sort, стр. 170–173.
  15. ^ Киркпатрик и Райш (1984); Альберс и Хагеруп (1997).
  16. ^ Киркпатрик и Райш (1984).
  17. ^ Андерссон и др. (1998).
  18. ^ Хан (2004).
  19. ^ Thorup (2002)
Вторичные источники
  • Чоудхури, Резаул А. (2008), «Эквивалентность очередей приоритета и сортировки», в Као, Мин-Ян (ред.), Энциклопедия алгоритмов, Springer, стр. 278–281, ISBN  9780387307701.
  • Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штейн, Клиффорд (2001), Введение в алгоритмы (2-е изд.), MIT Press и Макгроу-Хилл, ISBN  0-262-03293-7.
  • Гудрич, Майкл Т.; Тамассия, Роберто (2002), "4.5 Bucket-Sort and Radix-Sort", Разработка алгоритмов: основы, анализ и примеры в Интернете, John Wiley & Sons, стр. 241–243..
Основные источники