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

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

Широко використовуються практичні алгоритми цілочисельного сортування, такі як сортування Діріхле (англ. Pigeonhole), сортування підрахунком і сортування за розрядами. Інші алгоритми цілочисельного сортування, з меншими оцінками найгіршого випадку, не вважаються практичними для комп'ютерних архітектур, які мають 64 й менше бітів на слово. Відомо багато таких алгоритмів, швидкодія яких залежить від комбінації кількості об'єктів, що підлягають сортуванню, кількості бітів на ключ і кількості бітів на слово у комп'ютері, який виконує алгоритм сортування.

Загальні міркування

Моделі обчислень

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

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

Сортування в порівнянні з цілочисельною чергою з пріоритетом

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

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

Використовність

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

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

Практичні алгоритми

Сортування Діріхле або сортування підрахунком можуть сортувати n елементів даних, що мають ключі в діапазоні від 0 до K − 1, за час O(n + K). У сортуванні Діріхле (часто називають сортуванням комірками), вказівники на елементи даних розподілені по таблиці комірок, що представлені як типи даних, такі як зв'язані списки, використовуючи ключі як індекси в таблиці. Далі всі елементи об'єднуються разом, щоб сформувати вихідний список. Сортування підрахунками використовує таблицю лічильників замість таблиці комірок, щоб визначити кількість елементів з кожним ключем. Далі використовується обчислення префіксної суми для визначення діапазону позицій у відсортованих вихідних даних, на якому повинні бути розміщені значення з кожним ключем. Нарешті, у другому проході над вхідними даними, кожен елемент переміщується до позиції ключа у вихідному масиві. Обидва алгоритми включають тільки прості цикли над вхідними даними (за час O(n)) та над множиною можливих ключів (за час O(K)), даючи загальний час O(n + K).

Сортування за розрядами — це алгоритм сортування, який працює для більших ключів, ніж сортування Діріхле, або сортування підрахунками, шляхом виконання декількох проходів над даними. При кожному проході вхідні дані сортуються використовуючи лише частину ключів, використовуючи інший алгоритм сортування (такий як сортування Діріхле, або сортування підрахунками), які підходять лише для малих ключів. Щоб розбити ключі на частини, алгоритм сортування за розрядами обчислює позиційну систему для кожного ключа, відповідно до деякого обраного розряду; далі, частина ключа, що використовується для i-го проходження алгоритму э i-ю цифрою у позиційній системі для повного ключа, починаючи з найменш значущої, та переходячи на найбільш значущої цифри. Для того, щоб цей алгоритм працював коректно, алгоритм сортування, що використовується при кожному проході над даними, повинен бути стабільним: елементи з однаковими цифрами не повинні змінювати позиції один з одним. Для найбільшої ефективності розряд повинен бути вибраний близько до кількості елементів даних, n. Крім того, використання ступенів двійки близьких до n як розряду, дозволяє ключам для кожного проходу бути швидко обчисленими, використовуючи тільки швидкі бінарні операції зсуву і маски. За допомогою цих варіантів, а також за допомогою сортування Діріхле або сортування підрахунками як базового алгоритму, сортування за розрядами може відсортувати n елементів даних які мають ключі в діапазоні від 0 до K − 1 за час O(n log_n K).

Теоретичні алгоритми

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

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

Дерево ван Емде Боаса може використовуватися, як черга з пріоритетом для сортування набору з 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). Як екстремальний екземпляр, якщо w ≥ K, і всі ключі різні, то набір ключів може бути відсортований за лінійний час, представлений як бітова мапа, з бітом 1 у положенні i, коли i є одним з отриманих ключів, а потім повторно видаляється найменш важливий біт. Неконсервативний алгоритм сортування 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), або рандомізації у вигляді хеш-таблиць.

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

Див. також

• Принцип Діріхле

Посилання

Первинні джерела

• Ajtai, M.; Fredman, M.; Komlós, J. (1984), Hash functions for priority queues, Information and Control, 63 (3): 217—225, doi:10.1016/S0019-9958(84)80015-7, MR 0837087.
• Albers, Susanne; Hagerup, Torben (1997), Improved parallel integer sorting without concurrent writing, Information and Computation, 136 (1): 25—51, doi:10.1006/inco.1997.2632, MR 1457693.
• Andersson, Arne; Hagerup, Torben; Nilsson, Stefan; Raman, Rajeev (1998), Sorting in linear time?, Journal of Computer and System Sciences, 57 (1): 74—93, doi:10.1006/jcss.1998.1580, MR 1649809.
• Andersson, Arne; Nilsson, Stefan (1998), Implementing radixsort, ACM Journal of Experimental Algorithmics, 3, doi:10.1145/297096.297136, MR 1717389.
• Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel (1999), Fusion trees can be implemented with AC⁰ instructions only, Theoretical Computer Science, 215 (1-2): 337—344, doi:10.1016/S0304-3975(98)00172-8, MR 1678804.
• Bhatt, P. C. P.; Diks, K.; Hagerup, T.; Prasad, V. C.; Radzik, T.; Saxena, S. (1991), Improved deterministic parallel integer sorting, Information and Computation, 94 (1): 29—47, doi:10.1016/0890-5401(91)90031-V, MR 1123154.
• Cole, R.; Vishkin, U. (1986), Deterministic coin tossing with applications to optimal parallel list ranking, Information and Control, 70 (1): 32—53, doi:10.1016/S0019-9958(86)80023-7.
• Comrie, L. J. (1929–1930), The Hollerith and Powers tabulating machines, Trans. Office Mach. Users’ Assoc., Ltd.: 25—37. Cited by Thorup, (2007) as an early source for radix sort.
• Fredman, Michael L.; Willard, Dan E. (1993), Surpassing the information-theoretic bound with fusion trees, Journal of Computer and System Sciences, 47 (3): 424—436, doi:10.1016/0022-0000(93)90040-4, MR 1248864.
• Fredman, Michael L.; Willard, Dan E. (1994), Trans-dichotomous algorithms for minimum spanning trees and shortest paths, Journal of Computer and System Sciences, 48 (3): 533—551, doi:10.1016/S0022-0000(05)80064-9, MR 1279413.
• Hagerup, Torben (1987), Towards optimal parallel bucket sorting, Information and Computation, 75 (1): 39—51, doi:10.1016/0890-5401(87)90062-9, MR 0910976.
• Han, Yijie (2004), Deterministic sorting in O(n log log n) time and linear space, Journal of Algorithms, 50 (1): 96—105, doi:10.1016/j.jalgor.2003.09.001, MR 2028585.
• Han, Yijie; Thorup, M. (2002), Integer sorting in O(n√log log n) expected time and linear space, Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002), IEEE Computer Society, с. 135—144, doi:10.1109/SFCS.2002.1181890.
• Kirkpatrick, David; Reisch, Stefan (1984), Upper bounds for sorting integers on random access machines, Theoretical Computer Science, 28 (3): 263—276, doi:10.1016/0304-3975(83)90023-3, MR 0742289.
• McIlroy, Peter M.; Bostic, Keith; McIlroy, M. Douglas (1993), Engineering Radix Sort (PDF), Computing Systems, 6 (1): 5—27.
• Pedersen, Morten Nicolaj (1999), A study of the practical significance of word RAM algorithms for internal integer sorting, Masters thesis, Department of Computer Science, University of Copenhagen, Denmark, архів оригіналу за 16 березня 2012, процитовано 26 лютого 2019.
• Rahman, Naila; Raman, Rajeev (1998), An experimental study of word-level parallelism in some sorting algorithms, Algorithm Engineering, 2nd International Workshop, WAE '92, Saarbrücken, Germany, August 20–22, 1998, Proceedings (PDF), Max Planck Institute for Computer Science, с. 193—203, архів оригіналу (PDF) за 19 серпня 2019, процитовано 26 лютого 2019.
• Reif, John H. (1985), An optimal parallel algorithm for integer sorting, Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), IEEE Computer Society, с. 496—504, doi:10.1109/SFCS.1985.9.
• Thorup, Mikkel (2002), Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise Boolean operations, Journal of Algorithms, 42 (2): 205—230, doi:10.1006/jagm.2002.1211, MR 1895974.
• Thorup, Mikkel (2003), On AC⁰ implementations of fusion trees and atomic heaps, Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003), New York: ACM, с. 699—707, MR 1974982.
• Thorup, Mikkel (2007), Equivalence between priority queues and sorting, Journal of the ACM, 54 (6): Art. 28, doi:10.1145/1314690.1314692, MR 2374029.
• Willard, Dan E. (1983), Log-logarithmic worst-case range queries are possible in space Θ(N), Information Processing Letters, 17 (2): 81—84, doi:10.1016/0020-0190(83)90075-3, MR 0731126.

Вторинні джерела

• Chowdhury, Rezaul A. (2008), Equivalence between priority queues and sorting, у Kao, Ming-Yang (ред.), Encyclopedia of Algorithms, Springer, с. 278—281, ISBN 9780387307701, архів оригіналу за 17 травня 2016, процитовано 26 лютого 2019.
• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
• Goodrich, Michael T.; Tamassia, Roberto (2002), 4.5 Bucket-Sort and Radix-Sort, Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, с. 241—243.