Цифрове сортування

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

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

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

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

  • (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, ківш роду є узагальнення, що є ефективнішим у просторі та часі.

Дивіться також[ред. | ред. код]

Цифровий принцип

Література[ред. | ред. код]

Посилання[ред. | ред. код]