Материал: Інформатика_1 (методи побудови алгоритмівта та їх аналіз)

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

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

199

помогою пристроїв, які називалися перфораторами, пробивали-ся дірки. На перфокарта у 80 колонках у певних позиціях мож­на було пробити до 12 дірок. Комбінації цих пробитих дірок від-повідали певному символу, тобто на кожній перфокарті можна було набити інформацію з 80 символів. Цифри від 0 до 9 кодува-лися дірками у відповідних рядках 0-9 у колонках, що відпові-дали даній цифрі (див. с. 50).

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

Ця ідея і лягла в основу алгоритму цифрового сортування масиву. Сформулюемо Е£.

Нехай задано масив цілих чисел, максимальна розрядність яких дорівнює d. Для прикладу розглянемо масив із 7 цілих трицифрових чисел:

329, 457, 657, 839, 436, 720, 355.

Розглянемо спочатку молодші розряди кожного елемента масиву. Там можуть бути цифри від 0 до 9. Розкладемо всі чис­ла на 10 стосів: у перший - числа, які мають молодшу цифру 0, у другий - 1, у третій - 2, і т. д., у десятий - 9 (мал. 85).

0123456789

Мал. 85

Тепер складемо стоси чисел знову разом, зберігаючи первин-ну послідовність чисел у кожному стосі відносно їх ПОСЛІДОВ-ності в заданому масиві:

720, 355, 436, 457, 657, 329, 839.

На другому кроці сортування будемо цей масив розкладати на стоси відповідно до цифр десятків кожного числа (мал. 86).

о

8

12 3 4 5 6 7

Мал. 86

Склавши отримані числа зі стосів один за одним, отримаємо: 720, 329, 436, 839, 355, 457, 657. 200

Залишився один останній крок для розкладання чисел по стосах відповідно до старших розрядів, тобто цифр сотень кож­ного числа (мал. 87).

0123456789

Мал. 87

Запишемо числа, отримані у стосах, зберігаючи їх порядок у масиві, з якого вони потрапили у ці стоси. Результатом буде відсортований масив чисел:

329, 355, 436, 457, 657, 720, 839.

За три кроки отримали результат роботи алгоритму цифро­вого сортування. Чому саме за три? Зрозуміло - це прямо по-в'язано з кількістю цифр у найбільшому числі. До оцінки ефек-тивності роботи даного алгоритму звернемося пізніше.

А зараз давайте спробуємо записати алгоритм цифрового сортування:

1) зарезервуватимісце для 10 додаткових масивівAg, A_v ...,Ад (довжина їх повинна збігатися з довжиною вхідного масиву, оскільки можна підібрати такий тест, щоб усі елементи вхід- ного масиву попали в один стос);

2) визначити розрядність найбільшого числа вхідного масиву; 3)визначити і = 1;

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

5. переписати числа з масивів А₀, А., ..., А₉ у вхідний масив, зберігаючи їх послідовність у додаткових масивах;

6. збільшити і на 1 і якщо і не перевищує розрядності най-більшого числа, то перейти до пункту 4.

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

(Пошук максимального елемента вхідного масиву.} read (х[1]); max :=х[1]; for i := 2 to n do begin

read (x[i]);

if x[i] > max then max :=x[i]; end;

201

d := 0; {Визначення розрядності максимального числа.)

while max > 0 do begin inc (d);

max := maxdiv 10 end; count := 1;

for i := 1 to d do {Порозрядний перегляд елементів масиву.}

begin

{Ініціалізація кількості елементів у масивахЛ₀, ...,А_д.) forj :=0to9dok[j] :=0;

for j : = 1 to n do {Розміщення елементів масиву x по масивам А₀,.... А₉.) begin

digit := (x[j] div count) mod 10; inc (k[digit]); A[digit][k[digit]]:=x[j] end; count := count * 10; {Визначення наступного розряду елементів масиву.} j := 1; {Злиття елементів з масивів А₀, ...,/1₉у масивх.}

for q := 0 to 9 do forw:= 1 to k[q] do begin

x[j]:=A[q][w]; inc(j) end; end;

Перейдемо до визначення оцінки ефективності роботи ал­горитму цифрового сортування елементів масиву. її можна об-рахувати, проаналізувавши наведений текст програми. Та частина програми, яка безпосередньо виконує сортування масиву, складається з двох вкладених циклів: перший for і := 1 to d do залежить від кількості знаків найбільшого числа заданого масиву, а другий for j := 1 to n do - від кількості елементів цього масиву. Усередині зовнішнього циклу є где один цикл for q := 0 to 9 do, який збирає елементи, розкладені по стосам, в один масив. Він загалом переглядає п елементів заданого масиву. Тому результатом такого аналізу перегляду п елементів масиву буде d(n + п) - 2dn. Оскільки величина d є значно малою порівняно з п (maxlongint = 2147483647), то оцінкою ефективності роботи алгоритму цифрового сортуван­ня можна вважати 0(п).

Цифрове сортування досить чутливе до кількості вхідних даних. Тому при тестуванні цього алгоритму необхідно вра-хувати саме цей фактор. Але традиційно коректність його робо­ти перевірятимемо при п > 100 на таких вхідних даних:

• вхідний масив уже впорядкований необхідним чином;

• вхідний масив є частково впорядкованим;

202

• вхідний масив упорядкований у зворотному порядку;

• елементи вхідного масиву розміщені випадковим чином.

/ Запитання для самоконтролю

1. Якою є історія застосування алгоритму цифрового сортуванкя?

2. У чому полягає ідея алгоритму цифрового сортування?

1. Продемонструйте на власному прикладі роботу алгоритму циф­рового сортування.

2. Сформулюйте алгоритм цифрового сортування у словесній формі.

3. Запишіть текст Pascal-програми, що реалізує алгоритм цифро­вого сортування одновимірного масиву.

4. Проаналізуйте переваги й обмеження щодо використання мето­ду цифрового сортування.

5. Якою є оцінка ефективності роботи алгоритму, що реалізує ме­тод цифрового сортування одновимірного масиву? Обґрунтуйте свою відповідь.

Завдання

1. Реалізувати у вигляді прогреми алгоритм цифрового сор­тування заданої послідовності за зростанням.

2. Модифікувати алгоритм, реалізований у завданні 1, так, гцоб сортування відбувалося за спаданиям.

3. Протестувати реалізовані у завданнях 1-2 алгоритми для масиву 15, 4, 10, 8, 6, 9, 16, 1, 7, 3, 11, 14, 2, 5, 12, 13.

4. Проаналізувати покрокове виконання завдання 3 щодо кількості виконуваних дій.

5. Шдібрати власні тести, які доводить переваги й показу-ють недоліки методу цифрового сортування при п > 100.

6. Зробити письмовий аналіз завдань 3-5.

ПОРІВНЯННЯ МЕТОДІВ СОРТУВАННЯ

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

Для того щоб порівняння алгоритмів, що реалізують відпо-відні методи сортування, було достатньо наочним, заноситиме-мо час їх виконання в таблицю з параметрами, які визначають таке початкове формування елементів вхідного масиву: упо­рядкований за зростанням Growth, визначений випадковим чи­ном Random, упорядкований за спаданиям Decrease. Нага-дуемо, що робота всіх алгоритмів сортування спрямована на сортування вхідних масивів за зростанням.

203

Оскільки замір часу виконання алгоритмів залежить не лише від кількості елементів масивів, а й від технічних харак­теристик комп'ютера, на якому вони тестувалися, то зазначи-мо, що тестування відбувалося на комп'ютері AMD Duron, 1.00 ГТц, 128 МБ ОЗУ. Вибір саме такого комп'ютера спри-чинено тим, що на потужніших комп'ютерах досить важко за-фіксувати час виконання програм, що реалізують «швидкі» алгоритми, особливо ті, які певним чином обмежують кіль-кість оброблювальних елементів (наприклад, сортування за лі-нійний час). I навпаки, на «повільніших» машинах ыеможливо дочекатися результату роботи програм, що реалізують прямі методи сортування.

Як уже зазначалося, для фіксації часу роботи програми, що реалізує розроблений алгоритм, можна застосувати таку змінну:

var timer: longint absolute $40: $6c.

Зазначимо також (див. с. 23), що під час тестування програм фіксувався «чистий» час їх роботи, тобто не враховувалося вве­дения вхідної інформації та виведення результуючого відсорто-ваного масиву. Тобто загальний вигляд програми був таким:

timeold := timer;

<програма>

writeln ((timer - timeold) /18. 2);

Під час тестування виявилося, що на обраному комп'ютері не для всіх тестів і не для всіх алгоритмів вдалося зафіксувати час. При такій ситуації в таблицю заносився коментар «no time». I ще: для спрощення замість log₂n будемо вказувати logn.

Шсля обговорення всіх технічних питань перейдемо безпосе-редньо до проведения порівняння методів сортування (табл. 19).

Таблица 19

204

Продовження таблиці 19

205

Продовжепня таблиці 19