Немає перевірених версій цієї сторінки ймовірно її ще не перевіряли на відповідність правилам проекту Цифрове сортування

Немає цієї сторінки; ймовірно, її ще не перевіряли на відповідність правилам проекту.

Цифрове сортування, також відомий як граф роду (не плутати з підрахунком роду), є алгоритм сортування, який підходить для сортування списків елементів, в яких кількість елементів (n) і число можливих значень ключа (N) приблизно ж вона вимагає O(n + N) часу.

Алгоритм працює наступним чином:

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

Наприклад, припустимо, що ми розбирали ці пари значень їх першого елемента:

(5, "hello")
(3, "pie")
(8, "apple")
(5, "king")

Для кожного значення між 3 і 8 ми створюємо список, а потім перемістимо кожен елемент до його класу:

3: (3, "pie")
4:
5: (5, "hello"), (5, "king")
6:
7:
8: (8, "apple")

Потім ми переберемо масив в порядку і перемістіть їх назад в початковий список.

Різниця між осередками сортування і підрахунку роду є те, що при підрахунку роду, допоміжний масив не містить списки вхідних елементів, тільки має значення:

3: 1
4: 0
5: 2
6: 0
7: 0
8: 1

Використовуючи цю інформацію ми можемо виконати ряд обмінів на вхід масив, який ставить його в порядку, переміщення елементів тільки один раз.

Для масивів, де N набагато більше, ніж n, ківш роду є узагальнення, що є ефективнішим у просторі та часі.

Див. також

Література

Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — .(англ.)

Посилання

Візуалізатор 1 — Java-аплет.
Візуалізатор 2 — Java-аплет.