Мал. 84
Бачимо, що вже після першого проходу послідовність еле-ментів стала впорядкованою. Тому все-таки ефективніше на кожному кроді сортування заданої послідовності визначати реальну кількість серій і, коли вона досягне значения 1, завер-шити роботу алгоритму.
Якою може бути реалізація описаного алгоритму? Це за-лежить від уподобань кожного окремого програміста.
На першому кроці реалізації алгоритму (під час уведення елементів масиву) можна визначати індекси початку й кінця кожної серії. Цю інформацію можна записувати в масив, кожним елементом якого буде запис із двох значень.
У класичному варіанті алгоритму після кожного проходу злиття двох сусідніх серій приводить до того, що початком ново! серії буде індекс початку першої з них, а кінцем - кінець другої. Таким чином приберемо одну із серій. Зверніть увагу на те, що поки що ми не говоримо про те, як це зробити на рівні програмування!
Чи зменшувати при цьому кількість серій удвічі? На приклад! (мал. 83) бачимо, що в цьому немае сенсу, оскільки це може спричинити виконання зайвих проходів при сортуванні. Для того щоб обійти таку недоречність, можна після визначен-ня нових меж серій, що будуть надалі зливатися, перевірити наявність відношення о» < ajkrV Це означатиме, що останній елемент fe-ї серії не більший за перший елемент (ft + 1)-ї серії, тобто їх зливати немае потреби, оскільки вони вже утворюють злиту підпослідовність. Цей факт необхідно врахувати під час підрахунку кількості серій для поточного проходу масиву. Якщо в результата кількість серій стане 1, то це означатиме, що алгоритм природного злиття завершено, а отримана послідов-ність буде впорядкованою.
193
Запишемо реалізацію алгоритму сортування послідовності методом природного злиття у виг ляд і тексту Pascal-програми.
Спочатку розглянемо реалізацію частини алгоритму, яка виконує введения елементів послідовності й одночасно визна-чає межі впорядкованих серій за неспаданням. Для цього ре-зервується масив k: array[1..n] of record st, en: <тип> end.
{Початок першої серії.}
count := 1; read(a[1]); k[count].st := 1; i:=2;
while i <= n do begin
read (a[i]);
while (a[i - 1] <= a[i]) and (i <= n) do {Визначення поточно? cepil.} begin inc(i); read (a[i]) end; if i <= n then begin
k[count] .en := i - 1; {Кінець поточноі серії.)
inc(count); {Збільшення лічильника кількості серій.}
k[count] .st := і; {Початок наступноТ серії.}
Іпс(і) {Перехід до наступного елемента послідовності.)
end
{Кінець останньоі серії.}
else k[count].en := n;
end;
Алгоритм злиття серій, що визначені в поточному масиві one i записуються у масив two, можна реалізувати у вигляді та-кої процедури:
procedure merging (var one, two: mas); varq, x, у: <тип > ; begin
X := k[i].St; {Початок/-Ї cepii.}
у := k[i + 1 ].st; {Початок [I + 1 )-i cepii.)
for q :=k[i].stto k[i + 1].endo {Злиття і'-їта (/+1)-їсерій.)
{Умова наявності елементів в /'-й та (/ + 1 )-й серіях.)
if (x<=k[i].en)and(y<=k[i + 1].en)
then
if (опе[х]<ОПЄ[у]) {Результатом злиття на g-му кроці є)
{елемент /-Ї серіі;) then begin two[q] := one[x]; inc (x) end
{елемент (/' + 1 )-i cepii.) else begin two[q] := one[y]; inc (y) end else {Коли відсутні елементи в)
if X > к[І].ЄП {/-й серії, то дописуємо елементи (/ + 1)-їсерГІ.}
then begin two[q] := one[y]; inc (y) end
194
end;
{(/ + 1 )-й серії, то дописуємо елементи і-ї серіТ.} else begin two[q] := onefx]; inc (x) end;
Остаточний варіант алгоритму природного злиття може ви-глядати так:
flag := true;
{Повторения алгоритму злиття, поки кількість серій більша за 1.} while count > 1 do begin
{new_count - лічильник ново! кількості серій після злиття.) і := 1; newcount := 1;
while Kcount do {Перегляд i злиття поточної кількості серій.)
begin if flag
then merger (a, b) {Злиття серій з масиву а в масив to.)
else merger (b, а); {Злиття серій з масиву b в масив а.)
{Початок серії, що є результатом поточного злиття.) k[new_count].st := k[i].st;
{Кінець серіі. що є результатом поточного злиття.) k[new_count].en := k[i + 1].en;
inc(i, 2); {Перехіддонасгупноїпари серій.)
inc(newcount); (Збільшення лічильника злитих серій.)
end;
{Якщо лишився незлитий фрагмент масиву, то) if k[new_count - 1 ] .en < n {фіксуємо його початок i кінець у масиві к) then begin
k[new_count].st := k[new_count - 1].en + 1; k[new_count].en := n; if flag
then for j := k[new_count - IJ.en + 1 to n do
b[j] := a[j] {i дописуемо його елементи в масив to}
else for j := k[new_count - 1].en + 1 to n do
a[j] := b[j] {або в масив a.)
end
{У протилежному випадку зменшуємо кількість серій.) else dec(newcount); item := 1; {Підготовка до перерахунку поточної кількості серій.)
for q := 2 to newcount do {Якщо останній елемент не більший, ніж перший елемент сусідніх серій, то) if a[k[item].en] <= a[k[q].st]
then k[item].en := k[q].en {вважатимемо ці серіїоднією серією,)
else inc(item); {інакше переходимо до наступно? серії.)
new_COUnt := item; {Фіксація остаточного підрахунку кількості серій.)
{Перенесения остаточної кількості серій у відповідну змінну.)
count := new_count;
flag := not flag {Перемикання «вхідного» та «вихідного» масивів.)
end;
195
Перейдемо до оцінки ефективності роботи алгоритму, що реалізує метод природного злиття. Як уже пересвідчилися, при кожному проході в загальному випадку кількість серій змен-шується вдвічі, тому загальна кількість пересилань елементів у найгіршому випадку дорівнює п ■ [log2n], а в середньому може бути навіть і меншою. Однак насправді кількість порівнянь значно більша, ніж зазначена для пересилань. Це обумов-люється тим, що, крім порівнянь, необхідних для відбору еле-ментів при злитті, потрібні ще додаткові: між послідовними елементами кожної серії для того, щоб визначити її межі. Тому в загальному випадку можна вважати оцінку ефективності виконання алгоритму природного злиття такою: 0(п ■ [log2n]).
Оскільки метод природного злиття особливо чутливий до частково впорядкованих послідовностей вхідних даних, то при його тестуванні необхідно пересвідчитися саме у цьому на таких вхідних даних:
вхідний масив уже впорядкований необхідним чином;
вхідний масив є частково впорядкованим;
вхідний масив упорядкований у зворотному порядку;
елементи вхідного масиву розміщені випадковим чином. При формуванні вхідних послідовностей різної довжини
треба врахувати специфіку використання додаткових масивів при сортуванні методом природного злиття та узгодити типи вхідних даних із значениям п(п> 100).
/ Запитання для самоконтролю
1.У чому полягає ідея алгоритму сортування послідовності еле-ментів методом природного злиття?
Що називається серією послідовності? Якими мають бути від-ношення між сусідніми елементами максимально! серії послі-довності?
Зобразіть схематично алгоритм сортування послідовності методом природного злиття.
Обґрунтуйте призначення фаз розподілу та злиття елементів послідовності при кожному м проході.
Наведіть власний приклад послідовності та продемонструйте покроково роботу алгоритму природного злиття.
Сформулюйте алгоритм природного злиття у словесній формі.
Як у класичному випадку змінюватиметься кількість серій при кожному наступному проході?
За рахунок чого можна покращити ефективність роботи алгоритму природного злиття? Обґрунтуйте свою відповідь, запро-понувавши власний приклад послідовності.
Запишітьалгоритм методу природного злиття елементів посл-довності у вигляді тексту Pascal-програми.
196
10. Якою є оцінка ефективності роботи алгоритму природного злиття? Обґрунтуйте свою відповідь.
Завдання
Реалізувати у вигляді програми алгоритм сортування задано! послідовності за зростанням методом природного злиття.
Модифікувати алгоритм, реалізований у завданні 1, так, щоб сортування відбувалося за спаданиям.
Протестувати реалізовані в завданнях 1-2 алгоритми для масиву 15, 4, 10, 8, 6, 9, 16, 1, 7, 3, 11, 14, 2, 5, 12, 13.
Проаналізувати покрокове виконання завдання 3 щодо кількості виконуваних дій.
Шдібрати власні тести, які доводить переваги й показу-ють нєдоліки методу природного злиття при л > 100.
Зробити письмовий аналіз завдань 3-5.
СОРТУВАННЯ ЗА ЛІНІЙНИЙ ЧАС
Ми розглянули достатню кількість різних методів сортування. Усі воыи мають певні переваги й недоліки. Аналізуючи кожний із цих методів, ми намагалися оцінювати доцільність їх використання у кожній конкретній ситуації, давали оцінку ефективності виконання алгоритмів, що реалізують метод. Найгіршою була оцінка 0(п2), а найкращою - 0(п ■ \og2n).
Але виявляється, що це не найкращий варіант ефективності алгоритму. Розглянемо два методи, які виконують сортування за лінійний час, тобто оцінка їх ефективності О(п).
Чому ж ми не почали відразу з цих алгоритмів? Чому напи-сані цілі трактата стосовно аналізу та порівняння різних іс-нуючих методів сортування? Чому продовжуються пошуки ін-ших, кращих методів? Справа в тому, що ці методи, крім такої значної переваги, як виконання сортування за лінійний час, мають досить суттєві недоліки. Краще назвемо ці недоліки об-меженнями на застосування даних алгоритмів до тих чи інших масивів значень.
Якщо наперед відомий проміжок зміни значень елементів масиву, що впорядковується, то виявляється, що зовсім немає потреби в цьому впорядкуванні. Потрібно лише під час читан-ня елементів вхідного масиву підраховувати кількість можли-вих значень елементів, що ввійшли в конкретний масив.
Саме умова належності значень елементів масиву, що впо-рядковується, наперед відомому проміжку і є обмеженням на використання даного алгоритму.
Для такого підрахунку слід передбачити існування масиву, кількість елементів у якому дорівнюватиме кількості можли-вих значень елементів заданого масиву, а індекси збігатимуть-ся з цими значениями.
197
Розглянемо приклад масиву шкільних балів, які можуть змінюватися в межах від 1 до 12. Зрозуміло, що в описаному підході до впорядкування такого масиву заносити його в па-м'ять комп'ютера немае потреби. Достатньо покроково зчиту-вати елементи вхідної послідовності в деяку змінну х і зразу ж аналізувати це значения. Для фіксації кількості тих чи інших балів у вхідній послідовності зарезервуємо масив а., де і = 1, 2, ..., 12. Якщо х - 9, то значения ад збільшимо на 1. Зрозу-міло, що на початку роботи з масивом а необхідно всі його значения обнулити. Після завершения читання вхідної інфор-мації в масиві а буде вся необхідна нам інформація. Значениям елемента at буде кількість балів зі значениям і. Зрештою залишиться тільки роздрукувати числа і стільки разів, яким є значения самого елемента а(.
Загальний вигляд алгоритму у вигляді тексту Pascal-програ-ми значень вхідного масиву в проміжку [k; 1] виглядатиме так:
a: array[k.. I] of <зчислений тип>;
for i := k to I do
a[i]:=0; for i := 1 to n do begin
read (x); inc(a[x]) end; for i := k to I do if a[i]<>0then
forj := 1 toa[i] do write(i, ''); writeln;
Зрозуміло, що пей метод можна застосувати для будь-якої за довжиною послідовності вхідних значень. Вони можуть бути розміщені на диску у вхідному файлі, і прямо із файла будемо вести читання елементів.
Зробимо одне зауваження. Ми недарма в якості типу елемен-тів масиву а записали «зчислений тип». Справа в тому, що для елементів вхідного масиву типу real масив для підрахунку його елементів зарезервувати неможливо. Обґрунтуйте це твер-дження самостійно.
За традицією введемо оцінку ефективності роботи алгоритму сортування масиву методом підрахунку. Для даного методу вона становить О(п).
Оскільки сортування підрахунком абсолютно не залежить від упорядкованості чи неупорядкованості вхідних даних, то в цьому можна пересвідчитися при тестуванні саме на таких вхідних даних:
198
вхідний масив уже впорядкований необхідним чином;
вхідний масив є частково впорядкованим;
вхідний масив упорядкований у зворотному порядку;
елементи вхідного масиву розміщені випадковим чином. При тестуванні різних вхідних даних, що впорядковуються
алгоритмом підрахунку, обов'язково треба врахувати те, що робота даного алгоритму не стільки чутлива до довжини цих вхідних даних, скільки до діапазону зміни їх значень. Тому не-обхідно згенерувати такі послідовності вхідних даних для л > 100, щоб діапазон зміни їх значень давав змогу використа-ти метод сортування підрахунком.
/ Запитання для самоконтролю
Які фаю ори впливають на вибір тих чи інших методів сортування елементів масивів та на ефективність роботи цих алгоритмів?
У чому полягає ідея сортування елементів масиву методом пщрахунку?
Які обмеження накладаються на значения елементів масиву, що сортується методом пщрахунку?
Чи є обмеження на кількість елементів масиву, який сортується методом пщрахунку?
Чи є обмеження на тип елементів масиву, який може бути від-сортований методом пщрахунку?
Запишіть алгоритм і текст Pascal-програми, що реалізує сортування масиву методом пщрахунку.
Якою є оцінка ефективності роботи алгоритму сортування масиву методом пщрахунку?
Завдання
Реалізувати у вигляді програми алгоритм сортування задано'! послідовності за зростанням методом підрахунку.
Модифікувати алгоритм, реалізований у завданні 1, так, щоб сортування відбувалося за спаданиям.
Протестувати реалізовані в завданнях 1-2 алгоритми для масиву 15, 4, 10, 8, 6, 9, 16, 1, 7, 3, 11, 14, 2, 5, 12, 13.
Проаналізувати покрокове виконання завдання 3 щодо кількості виконуваних дій.
Підібрати власні тести, які доводять переваги й показу-ють недоліки методу сортування підрахунком при п > 100.
Зробити письмовий аналіз завдань 3-5.