Алгоритм ціфровойсортіровкі (radix sort) використовувався в машинах для сортування перфокарт. У картонних перфокартах спеціальний перфоратор пробивав дірки. У кожній з 80 колонок були місця для 12 прямокутних дірок.
Сортувальної машин ?? е вказували стовпець, по якому потрібно провести сортування, і вона розкладала колоду перфокарт на 10 стопок виходячи з того, яка з дірок 0-9 була пробита в зазначеному стовпці.
Як впорядкувати колоду перфокарт з багатозначними числами (розряд одиниць в одному стовпці, десятків - в попередньому і т.д.)? Перше, що спадає на думку, - почати сортування зі старшого розряду. При цьому вийде 10 стопок, кожну з яких на наступному кроці доведеться розбивати на 10 стопок, і так далі - вийде велика кількість чарок перфокарт.
Як не дивно, виявляється зручніше почати з молодшого розряду, розклавши колоду на 10 стопок виходячи з того, де пробито отвір в''млад-шем'' стовпці. Отримані 10 стопок потрібно після цього скласти в одну в такому порядку: спочатку карти з 0, потім карти з 1, і т. Д. Отриману колоду знову розсортуємо на 10 стопок, але вже відповідно до розряду десятків, складемо отримані стопки в одну колоду , і т.д.; якщо на перфокартах були записані''d - значні числа, то знадобиться d раз скористатися сортувальної машиною. На рис. 2.9 показано, як діє цей алгоритм, застосований до семи тризначним числах.
Малюнок 2.9 - Приклад цифровий сортування тризначних чисел
На малюнку показаний вихідний порядок чисел, а також після сортування по третій, другий і першої цифрам (вертикальні стрілки вказують, по якій цифрі проводилася сортування).
Важливо, щоб алгоритм, за допомогою якого відбувається сортування по даному розряду, був стійким: картки, у яких в даному стовпчику стоїть одна і та ж цифра, повинні вийти з сортувальної машини в тій же після-довательности, в якій вони туди подавалися.
У комп'ютерах цифрова сортування іноді використовується для впорядкування даних, що містять кілька полів. Нехай, наприклад, потрібно впорядкувати послідовність дат. Це можна зробити за допомогою будь-якого алгоритму сор-вання, порівнюючи дати наступним чином: порівняти роки, в разі якщо роки збігаються - порівняти місяці, в разі якщо збігаються і місяці - порівняти числа. Замість цього, однак, можна просто тричі впорядкувати масив дат за допомогою стійкого алгоритму: спочатку по днях, потім по місяцях, потім по роках.
Програму для цифрової сортування написати легко. Передбачається, що кожен елемент n -елементного масиву А складається з d цифр, причому цифра номер 1-молодший розряд, а цифра номер d - старший.
Лістинг 2.10 - Алгоритм цифрової сортування
У разі якщо цифри можуть набувати значень від 1 до k, де k чи не занадто велике, то очевидний вибір - сортування підрахунком. Для п чисел з d знаками від 0 до k - 1 кожен прохід займає час Q (n + k); оскільки ми робимо d проходів, час роботи цифрової сортування одно Q (d × n + k × d). У разі якщо d постійно і k = О (п), то цифрова сортування працює за лин ?? ейное час.
При цифровий сортування важливо правильно вибрати підставу системи числення, оскільки від нього залежить розмір необхідної додаткової пам'я-ти і час роботи. Конкретний приклад: нехай потрібно впорядкувати мільйон 64-бітних чисел. У разі якщо розглядати їх як чотиризначні числа в системі числення з основою 2 16. то при цифровий сортування знадобиться нд ?? його чотири проходу, при використанні в процедурі Counting-Sort масиву В розміром 2 16 (що небагато в порівнянні з розміром сортованого масиву) . Це вигод-но відрізняється від сортування порівнянням, коли на кожне число припадає по log n'' 20 операцій. На жаль, цифрова сортування, яка спирається на сортування підрахунком, вимагає ще одного масиву (того ж розміру, що і сортований) для зберігання проміжних результатів, в той час як мно-Гії алгоритми сортування порівнянням обходяться без цього. З цієї причини, у разі якщо потрібно економити пам'ять, алгоритм швидкого сортування може виявитися віддай перевагу-тельнее.