Цифрове сортування
Цифрове сортування, також відомий як граф роду (не плутати з підрахунком роду), є алгоритм сортування, який підходить для сортування списків елементів, в яких кількість елементів (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, ківш роду є узагальнення, що є ефективнішим у просторі та часі.
Див. також
Цифровий принцип
Література
- Дональд Кнут. Мистецтво програмування, том 3. Сортування та пошук = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е вид. — «Вільямс», 2007. — С. 824. — ISBN 5-8459-0082-4.
Посилання
- Візуалізатор 1 — Java-аплет.
- Візуалізатор 2 — Java-аплет.