Цілочисельне сортування в інформатиці — це алгоритмічна задача сортування набору значень за числовими ключами, кожен з яких є цілим числом. Алгоритми, призначені для цілочисельного сортування, також можуть часто застосовуватися до задач сортування, в яких ключі — числа з рухомою комою, раціональні числа або текстові рядки.. В багатьох випадках можливість виконання цілочисельної арифметики з ключами дозволяє цілочисельним алгоритмам сортування виконуватись швидше, ніж алгоритмам сортування порівняннями, але це залежить від того, які операції дозволені в моделі обчислень і наскільки великими можуть бути цілі числа.
Широко використовуються практичні алгоритми цілочисельного сортування, такі як сортування Діріхле (), сортування підрахунком і сортування за розрядами. Інші алгоритми цілочисельного сортування, з меншими оцінками найгіршого випадку, не вважаються практичними для комп'ютерних архітектур, які мають 64 й менше бітів на слово. Відомо багато таких алгоритмів, швидкодія яких залежить від комбінації кількості об'єктів, що підлягають сортуванню, кількості бітів на ключ і кількості бітів на слово у комп'ютері, який виконує алгоритм сортування.
Загальні міркування
Моделі обчислень Оцінки часу для алгоритмів цілочисельного сортування зазвичай залежать від трьох параметрів: число — кількість значень, що підлягають сортуванню, величина — найбільший можливий ключ для сортування та число — кількість бітів, які можуть бути представлені в одному машинному слові комп'ютера, на якому повинен виконуватися алгоритм. Як правило, передбачається, що ; тобто, машинні слова достатньо великі, щоб представляти індекс у послідовності вхідних даних, а також досить великі, щоб представляти єдиний ключ..
Алгоритми цілочисельного сортування зазвичай розроблені для роботи c моделями обчислень в (), або в машині з довільним доступом. Основна відмінність між цими двома моделями полягає в тому, як пам'ять може бути адресована. Машина довільного доступу дозволяє будь-яке значення, яке зберігається в регістрі, використовувати як адресу операцій зчитування та запису пам'яті, з одиничною вартістю операції. Це дозволяє швидко реалізовувати певні складні операції над даними за допомогою пошуку в таблиці. З іншого боку, в моделі машини вказівника операції зчитування і запису використовують адреси, що зберігаються в вказівниках, і не дозволяється виконувати арифметичні операції над цими вказівниками. В обох моделях можна додавати значення даних, виконувати побітові булеві операції і двійкові операції зсуву над ними за одиницю часу на операцію. Проте, різні алгоритми цілочисельного сортування роблять різні припущення щодо того, чи має цілочисельне множення як операція одиничну вартість.The question of whether integer multiplication or table lookup operations should be permitted goes back to ; see also . Також розглядаються інші більш спеціалізовані моделі обчислень, такі як паралельна машина з довільним доступом.; comment in ; ; ; . показали, що в деяких випадках множення або пошук в таблицях, які необхідні для деяких алгоритмів цілочисельного сортування, можуть бути замінені спеціальними операціями, які легше реалізуються в апаратних засобах, але зазвичай не доступні на комп'ютерах загального призначення. покращив це, показавши, як замінити ці спеціальні операції на інструкції з маніпулювання бітовими полями, які вже доступні на процесорах Pentium.
Сортування в порівнянні з цілочисельною чергою з пріоритетом Черга з пріоритетами () — це структура даних для збереження колекції елементів з числовими пріоритетами, що має операції пошуку та видалення елемента з мінімальним значенням пріоритету. Черги з пріоритетом, засновані на порівняннях, такі як бінарна купа, потребують логарифмічного часу на оновлення, але такі структури, як дерево ван Емде Боаса, або черга з пріоритетом з обмеженою висотою (), можуть бути швидшими для вхідних даних, у яких пріоритетами є малі цілі числа. Ці структури даних можуть бути використані в алгоритмі сортування вибором, який сортує набір елементів шляхом багаторазового пошуку і видалення найменшого елемента з колекції та поверненням елементів в порядку, в якому вони були знайдені. Черга з пріоритетами може використовуватися в цьому алгоритмі для збереження колекції елементів і час для цього алгоритму, для колекції з елементів, може бути обмеженим часом для ініціалізації черги пріоритету, а потім виконуванням операцій пошуку і видалення. Наприклад, використання бінарної купи, як черги пріоритету у сортуванні вибором, призводить до алгоритму пірамідального сортування, алгоритму, на основі порівнянь, який займає час . Замість цього, якщо використовувати чергу з пріоритетом з обмеженою висотою в сортуванні вибором, це призводить до форми сортування Діріхле, а використання дерева ван Емде Боаса, або інших цілочисельних черг з пріоритетами призводить до інших алгоритмів швидкого сортування.
Замість використання цілочисельної черги з пріоритетами в алгоритмі сортування, можна використовувати алгоритми цілочисельного сортування, як підпрограми в структурі даних цілочисельної черги з пріоритетами. використовував цю ідею, щоб показати, що, якщо можливо виконати цілочисельне сортування за час на ключ, тоді однакове обмеження часу застосовується до часу на операцію вставки, або видалення в структурі даних черги з пріоритетами. Скорочення Торупа () є складним і передбачає наявність або швидких операцій множення, або пошуку в таблиці, але він також надає альтернативну чергу з пріоритетами, яка використовує тільки операції додавання та булеві операції з часом за операцію — максимальне множення часу на повторний логарифм.
Використовність Класичні алгоритми цілочисельного сортування, такі як сортування Діріхле (), сортування підрахунком і сортування за розрядами; . широко використовуються та є досить практичними. Більшість подальших досліджень алгоритмів цілочисельного сортування менше зосереджувалася на практичності та більше на теоретичних вдосконаленнях в , і алгоритми, що виходять з цього напрямку дослідження, не вважаються практичними для сучасних 64-бітових архітектур комп'ютерів, хоча експерименти показали, що деякі з цих методів можуть бути поліпшенням у сортуванні за розрядами для даних з 128 або більше бітами на ключ.. Крім того, для великих наборів даних, використання моделей з майже довільним для багатьох алгоритмів цілочисельного сортування може завадити їх порівнянню зі схожими алгоритмами сортування, які були розроблені з орієнтацією на використання ієрархії пам'яті..
Цілочисельне сортування є одним з шести тестів продуктивності дискретної математики агентства передових оборонних дослідницьких проектів (DARPA) () для DARPA HPCS Discrete Mathematics Benchmarks , Duncan A. Buell, University of South Carolina, retrieved 2011-04-20. та одним з одинадцяти тестів продуктивності у комплекті тестів NAS Parallel Benchmarks.
Практичні алгоритми Сортування Діріхле або сортування підрахунком можуть сортувати елементів даних, що мають ключі в діапазоні від до , за час . У сортуванні Діріхле (часто називають сортуванням комірками), вказівники на елементи даних розподілені по таблиці комірок, що представлені як типи даних, такі як зв'язані списки, використовуючи ключі як індекси в таблиці. Далі всі елементи об'єднуються разом, щоб сформувати вихідний список.. Хоча також описує версію цього алгоритму сортування, але вона адаптована то вхідних даних, де ключі є дійсними числами з відомим розподіленням, на відміну від цілочисельного сортування Сортування підрахунками використовує таблицю лічильників замість таблиці комірок, щоб визначити кількість елементів з кожним ключем. Далі використовується обчислення для визначення діапазону позицій у відсортованих вихідних даних, на якому повинні бути розміщені значення з кожним ключем. Нарешті, у другому проході над вхідними даними, кожен елемент переміщується до позиції ключа у вихідному масиві., 8.2 Counting Sort, pp. 168—169. Обидва алгоритми включають тільки прості цикли над вхідними даними (за час ) та над множиною можливих ключів (за час ), даючи загальний час .
Сортування за розрядами — це алгоритм сортування, який працює для більших ключів, ніж сортування Діріхле, або сортування підрахунками, шляхом виконання декількох проходів над даними. При кожному проході вхідні дані сортуються використовуючи лише частину ключів, використовуючи інший алгоритм сортування (такий як сортування Діріхле, або сортування підрахунками), які підходять лише для малих ключів. Щоб розбити ключі на частини, алгоритм сортування за розрядами обчислює позиційну систему для кожного ключа, відповідно до деякого обраного розряду; далі, частина ключа, що використовується для i-го проходження алгоритму э i-ю цифрою у позиційній системі для повного ключа, починаючи з найменш значущої, та переходячи на найбільш значущої цифри. Для того, щоб цей алгоритм працював коректно, алгоритм сортування, що використовується при кожному проході над даними, повинен бути стабільним: елементи з однаковими цифрами не повинні змінювати позиції один з одним. Для найбільшої ефективності розряд повинен бути вибраний близько до кількості елементів даних, . Крім того, використання ступенів двійки близьких до як розряду, дозволяє ключам для кожного проходу бути швидко обчисленими, використовуючи тільки швидкі бінарні операції зсуву і маски. За допомогою цих варіантів, а також за допомогою сортування Діріхле або сортування підрахунками як базового алгоритму, сортування за розрядами може відсортувати елементів даних які мають ключі в діапазоні від до за час .; , 8.3 Radix Sort, pp. 170—173.
Теоретичні алгоритми Було розроблено багато цілочисельних алгоритмів сортування, теоретичний аналіз яких показує, що вони ведуть себе краще, ніж сортування порівняннями, сортування Діріхлє, або сортування за розрядами для великих комбінацій параметрів, що визначають кількість елементів, що підлягають сортуванню, діапазон ключів і розмір машинного слова. Який алгоритм має кращу продуктивність залежить від значень цих параметрів. Однак, всупереч їхнім теоретичним перевагам, ці алгоритми не є поліпшенням для типових діапазонів цих параметрів, які виникають у практичних задачах сортування.
Алгоритми для маленьких ключів Дерево ван Емде Боаса може використовуватися, як черга з пріоритетом для сортування набору з ключів, кожен в діапазоні від до , за час . Це є теоретичним поліпшенням порівняно з сортуванням за розрядами, коли є достатньо великим. Однак для того, щоб використовувати дерево ван Емде Боаса, потрібно або безпосередньо адресовану пам'ять з слів, або змоделювати його за допомогою геш-таблиці, зменшуючи простір до лінійного, але алгоритм стає випадковим. Ще однією чергою з пріоритетом з подібною продуктивністю (включаючи необхідність випадковості у вигляді геш-таблиць) є .