Цілочисельне сортування

Оцінки часу для алгоритмів цілочисельного сортування зазвичай залежать від трьох параметрів: число n — кількість значень, що підлягають сортуванню, величина K — найбільший можливий ключ для сортування та число w — кількість бітів, які можуть бути представлені в одному машинному слові комп'ютера, на якому повинен виконуватися алгоритм. Як правило, передбачається, що w ≥ log₂(max (n, K)); тобто, машинні слова достатньо великі, щоб представляти індекс у послідовності вхідних даних, а також досить великі, щоб представляти єдиний ключ.[2]

Алгоритми цілочисельного сортування зазвичай розроблені для роботи c моделями обчислень в машині вказівника (англ. Pointer machine), або в машині з довільним доступом. Основна відмінність між цими двома моделями полягає в тому, як пам'ять може бути адресована. Машина довільного доступу дозволяє будь-яке значення, яке зберігається в регістрі, використовувати як адресу операцій зчитування та запису пам'яті, з одиничною вартістю операції. Це дозволяє швидко реалізовувати певні складні операції над даними за допомогою пошуку в таблиці. З іншого боку, в моделі машини вказівника операції зчитування і запису використовують адреси, що зберігаються в вказівниках, і не дозволяється виконувати арифметичні операції над цими вказівниками. В обох моделях можна додавати значення даних, виконувати побітові булеві операції і двійкові операції зсуву над ними за одиницю часу на операцію. Проте, різні алгоритми цілочисельного сортування роблять різні припущення щодо того, чи має цілочисельне множення як операція одиничну вартість.[3] Також розглядаються інші більш спеціалізовані моделі обчислень, такі як паралельна машина з довільним доступом.[4] Andersson, Milterse та Thorup, (1999) показали, що в деяких випадках множення або пошук в таблицях, які необхідні для деяких алгоритмів цілочисельного сортування, можуть бути замінені спеціальними операціями, які легше реалізуються в апаратних засобах, але зазвичай не доступні на комп'ютерах загального призначення. Thorup, (2003) покращив це, показавши, як замінити ці спеціальні операції на інструкції з маніпулювання бітовими полями, які вже доступні на процесорах Pentium.

Черга з пріоритетами (англ. priority queue) — це структура даних для збереження колекції елементів з числовими пріоритетами, що має операції пошуку та видалення елемента з мінімальним значенням пріоритету. Черги з пріоритетом, засновані на порівняннях, такі як бінарна купа, потребують логарифмічного часу на оновлення, але такі структури, як дерево ван Емде Боаса, або черга з пріоритетом з обмеженою висотою (англ. bucket queue), можуть бути швидшими для вхідних даних, у яких пріоритетами є малі цілі числа. Ці структури даних можуть бути використані в алгоритмі сортування вибором, який сортує набір елементів шляхом багаторазового пошуку і видалення найменшого елемента з колекції та поверненням елементів в порядку, в якому вони були знайдені. Черга з пріоритетами може використовуватися в цьому алгоритмі для збереження колекції елементів і час для цього алгоритму, для колекції з n елементів, може бути обмеженим часом для ініціалізації черги пріоритету, а потім виконуванням n операцій пошуку і видалення. Наприклад, використання бінарної купи, як черги пріоритету у сортуванні вибором, призводить до алгоритму пірамідального сортування, алгоритму, на основі порівнянь, який займає час O(n log n). Замість цього, якщо використовувати чергу з пріоритетом з обмеженою висотою в сортуванні вибором, це призводить до форми сортування Діріхле, а використання дерева ван Емде Боаса, або інших цілочисельних черг з пріоритетами призводить до інших алгоритмів швидкого сортування.[5]

Замість використання цілочисельної черги з пріоритетами в алгоритмі сортування, можна використовувати алгоритми цілочисельного сортування, як підпрограми в структурі даних цілочисельної черги з пріоритетами. Thorup, (2007) використовував цю ідею, щоб показати, що, якщо можливо виконати цілочисельне сортування за час T(n) на ключ, тоді однакове обмеження часу застосовується до часу на операцію вставки, або видалення в структурі даних черги з пріоритетами. Скорочення Торупа (англ. Thorup's) є складним і передбачає наявність або швидких операцій множення, або пошуку в таблиці, але він також надає альтернативну чергу з пріоритетами, яка використовує тільки операції додавання та булеві операції з часом T(n) + T(log n) + T(log log n) + ... за операцію — максимальне множення часу на повторний логарифм.[5]

Класичні алгоритми цілочисельного сортування, такі як сортування Діріхле (англ. Pigeonhole), сортування підрахунком і сортування за розрядами[6] широко використовуються та є досить практичними. Більшість подальших досліджень алгоритмів цілочисельного сортування менше зосереджувалася на практичності та більше на теоретичних вдосконаленнях в аналізі найгіршої ситуації, і алгоритми, що виходять з цього напрямку дослідження, не вважаються практичними для сучасних 64-бітових архітектур комп'ютерів, хоча експерименти показали, що деякі з цих методів можуть бути поліпшенням у сортуванні за розрядами для даних з 128 або більше бітами на ключ.[7] Крім того, для великих наборів даних, використання моделей з майже довільним доступом до пам'яті для багатьох алгоритмів цілочисельного сортування може завадити їх порівнянню зі схожими алгоритмами сортування, які були розроблені з орієнтацією на використання ієрархії пам'яті.[8]

Цілочисельне сортування є одним з шести тестів продуктивності дискретної математики агентства передових оборонних дослідницьких проектів (DARPA) (англ. Defense Advanced Research Projects Agency) для високопродуктивних комп'ютерних систем[9] та одним з одинадцяти тестів продуктивності у комплекті тестів NAS Parallel Benchmarks.

Дерево ван Емде Боаса може використовуватися, як черга з пріоритетом для сортування набору з n ключів, кожен в діапазоні від 0 до K − 1, за час O(n log log K). Це є теоретичним поліпшенням порівняно з сортуванням за розрядами, коли K є достатньо великим. Однак для того, щоб використовувати дерево ван Емде Боаса, потрібно або безпосередньо адресовану пам'ять з K слів, або змоделювати його за допомогою геш-таблиці, зменшуючи простір до лінійного, але алгоритм стає випадковим. Ще однією чергою з пріоритетом з подібною продуктивністю (включаючи необхідність випадковості у вигляді геш-таблиць) є Y-fast trie Willard, (1983). Більш складний метод з подібною особливістю і з кращими теоретичними характеристиками розробили Kirkpatrick та Reisch, (1984). Вони зауважили, що кожен прохід сортування за розрядами може бути інтерпретований, як метод скорочення діапазону, який за лінійний час зменшує максимальний розмір ключа на коефіцієнт n; замість цього, їх метод зменшує розмір ключа до квадратного кореня з попереднього значення (зменшивши удвічі кількість бітів, необхідних для представлення ключа), знову за лінійний час. Як і в сортуванні за розрядами, вони інтерпретують ключі, як двозначні числа за основою b, що становить приблизно √K. Потім вони групують елементи, які необхідно відсортувати, у комірки (англ. buckets) відповідно до їх старших цифр, у лінійний час, використовуючи, або велику, але неініціалізовану пам'ять з прямим доступом, або геш-таблицю. У кожної комірки є представник, елемент в комірці з найбільшим ключем; потім вони сортують список елементів, використовуючи старші цифри для представників і молодші цифри для не представників, як ключі. Групуючи елементи з цього списку знову в комірки, кожна комірка може бути розташована у відсортованому порядку, і, витягаючи представників з відсортованого списку, комірки можуть бути об'єднані у відсортованому порядку. Таким чином, за лінійний час проблема сортування зводиться до іншої рекурсивної задачі сортування, в якій ключі значно менші, ніж квадратний корінь з їхньої попередньої величини. Повторення цього зменшення діапазону, поки ключі достатньо малі, щоб сортувати комірками, призводить до алгоритму з часом роботи O(n log log_n K).

Складний випадковий алгоритм Han та Thorup, (2002) в моделі обчислення машині з довільним доступом до слів дозволяє ці часові межі скорочувати ще далі, до O(n√log log K).

Алгоритм цілочисельного сортування вважається неконсервативним, якщо він вимагає розмір слова w, що значно перевищує log max(n, K).[13] Як екстремальний екземпляр, якщо w ≥ K, і всі ключі різні, то набір ключів може бути відсортований за лінійний час, представлений як бітова мапа, з бітом 1 у положенні i, коли i є одним з отриманих ключів, а потім повторно видаляється найменш важливий біт.[14] Неконсервативний алгоритм сортування Albers та Hagerup, (1997) використовує підпрограму, засновану на сортуванні бітонічної мережі Кеннета Бетчера, для об'єднання двох сортованих послідовностей ключів, кожна з яких досить коротка, щоб бути упакованими в одне машинне слово. Вхідні дані до запакованого алгоритму сортування — послідовність елементів, що зберігаються по одному слову, перетворюється в упаковану форму — послідовність слів, кожна з яких містить кілька елементів у відсортованому порядку, використовуючи цю підпрограму повторно, щоб подвоїти кількість елементів, упакованих у кожне слово. Після того, як послідовність набула упаковану форму, Albers and Hagerup використовують форму сортування злиттям, щоб відсортувати її; коли дві послідовності об'єднуються у довшу послідовність, таке ж саме бітонічне сортування може бути використано для повторного вилучення запакованих слів, що складаються з найменших залишившихся елементів двох послідовностей. Цей алгоритм отримує достатньо прискорення зі свого упакованого подання, щоб відсортувати свої вхідні дані за лінійний час коли це можливо для одного слова, що містить Ω(log n log log n) ключів, тобто, коли log K log n log log n ≤ cw для деякої константи c > 0.

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

Один із перших результатів у цьому напрямку отримали Ajtai, Fredman та Komlós, (1984) за допомогою моделі обчислень клітинного зонда (штучна модель, в якій складність алгоритму вимірюється тільки розміром доступної пам'яті, яку він використовує). Спираючись на свою роботу, Fredman та Willard, (1994) описали дві структури даних, Q-купу та атомну купу, які реалізуються на машині довільного доступу. Q-купа є біто-паралельною версією двійкового префіксного дерева і дозволяє як операціям пріоритетних черг, так і наступним та попереднім запитам виконуватися за постійний час для наборів з O((log N)^1/4) елементів, де N ≤ 2^w — це розмір попередньо обчислених таблиць, необхідних для реалізації структури даних. Атомна купа — це Б-дерево, у якому кожен вузол дерева представлено у вигляді Q-купи, це дозволяє виконувати операції черг з пріоритетами (і, отже, сортування) за постійний час для наборів з (log N)^O(1) елементів.

Andersson та ін., (1998) показали рандомізований алгоритм, який називається сортуванням сигнатурами, що дозволяє сортувати за лінійний час набори елементів кількістю до 2^{O((log w)1/2 − ε)} елементів, при умові будь-якої константи ε > 0. Як і в алгоритмі Кіркпатріка та Рейша, вони виконують зменшення діапазону, використовуючи представлення ключів, як числа з основою b для ретельного вибору b. Їх алгоритм зменшення діапазону замінює кожну цифру сигнатурою, яка є хешованим значенням з O(log n) бітами, так що різні значення цифр мають різні підписи. Якщо n є достатньо малим, числа, утворені цим процесом заміни, будуть значно меншими, ніж вихідні ключі, дозволяючи неконсервативному упакованому алгоритму сортування Albers та Hagerup, (1997) сортувати замінені числа за лінійний час. З відсортованого списку замінених чисел можна сформувати префіксне дерево ключів у лінійний час, та діти кожного вузла у цьому дереві можуть бути рекурсивно відсортовані, використовуючи тільки ключі розміру b, після чого обхід дерева дає відсортований порядок елементів.

Fredman та Willard, (1993) представили транс-дихотомічну модель аналізу для алгоритмів сортування цілих чисел у якій нічого не передбачається про діапазон цілочисельних ключів та має бути пов'язана з продуктивністю алгоритму за допомогою функції кількості елементів даних. З іншого боку, у цій моделі час роботи алгоритму на множині з n елементів вважається найгіршим часом виконання для будь-якої можливої комбінації значень K та w. Першим алгоритмом такого типу був алгоритм сортування fusion-деревом Фредмана та Уіларда, який сортує за час O(n log n / log log n); це поліпшення алгоритму сортування порівнянням для будь-якого вибору K та w. Альтернативна версія їх алгоритму, що містить використання випадкових чисел та операцій цілочисельного поділу, покращує це до O(n√log n).

З моменту їх роботи були розроблені ще кращі алгоритми. Наприклад, неодноразово застосовуючи методику зниження діапазону Кіркпатріка-Рейша, поки ключі не будуть достатньо малими, щоб застосувати упакований алгоритм сортування Альберса-Хагерупа, можна сортувати за час O(n log log n); однак, частина цього алгоритму, що відповідає за зменшення діапазону, вимагає або великого обсягу пам'яті (пропорційно до √K), або рандомізації у вигляді хеш-таблиць.[15]

Han та Thorup, (2002) показали, як сортувати за рандомізований час O(n√log log n). Їхня техніка передбачає використання ідей, пов'язаних з сортуванням сигнатурами, для розбиття даних на множину малих підсписків, розмір яких досить невеликий, щоб сортування сигнатурами могло ефективно сортувати кожен з них. Також можна використовувати подібні ідеї для сортування цілих чисел детерміновано за час O(n log log n) та у лінійному просторі.[16] Використовуючи лише прості арифметичні операції (без множення або пошуку в таблиці) можна сортувати за рандомізований очікуваний час O(n log log n)[17] або детерміновано за час O(n (log log n)^{1 + ε}) для будь-якої константи ε > 0.[1]