Що таке сортування за принципом із прикладом?

Алгоритм сортування Radix вимагає кількості проходів, які дорівнюють кількості цифр, присутніх у найбільшому числі зі списку чисел. Наприклад, якщо найбільше число є 3-значним, цей список сортується за 3 проходи.

Корінний сорт є алгоритм цілочисельного сортування, який сортує дані за допомогою цілочисельних ключів шляхом групування ключів за окремими цифрами, які мають однакову значущу позицію та значення (розрядне значення). Сортування за принципом використовує сортування підрахунком як підпрограму для сортування масиву чисел.

Сортування за принципом можна застосувати до дані, які можна відсортувати лексикографічно, будь то цілі числа, слова, перфокарти, гральні карти чи пошта.

1 Сортування телефонних номерів Наприклад, якщо у вас є список телефонних номерів у форматі +1-xxx-yyy-zzzz, ви можете використати сортування за основою, щоб відсортувати їх у порядку зростання, спочатку згрупувавши їх за останніми чотирма цифрами (zzzz), а потім за три середні цифри (yyy) і, нарешті, перші три цифри (xxx).

Radix Sort може сортувати все, що можна впорядкувати за лексикографією. Його асимптотична складність кроку в найгіршому випадку дорівнює O(wn), де w — довжина ключа сортування. Сортування злиттям може сортувати елементи на основі довільно великого ключа сортування, чого не може зробити Radix Sort.

У позиційній системі числення коренем (множ.: radices) або основою є кількість унікальних цифр, включаючи цифру нуль, які використовуються для представлення чисел. Наприклад, для десяткової системи (найпоширенішої системи, яка використовується сьогодні) система числення дорівнює десяти, оскільки в ній використовуються десять цифр від 0 до 9.