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

Шейкерне сортування

Шейкерне сортування ShakerSort (з ант. Shake - трясти) є покращенням методу обміну і базується на ідеї саме цього методу.

Почнемо із запитання: а чи не можна дещо покращити метод прямого обміну, з яким ми вже попередньо ознайомилися?

Для того щоб відповісти на це запитання, повернемося до прикладу, наведеного в таблиці 16. Шд час останніх трьох про-ходів по масиву не було зроблено жодного переставлення еле- I ментів! Про що це говорить? Зрозуміло, це означає, що масив уже впорядкований, а тому немає сенсу виконувати ці останні I кроки сортування. Отже, перше вдосконалення полягае в тому.

158

щоб здійснювати контроль щодо виконання хоча б одного пе-реставлення в останньому перегляді масиву. У випадку його відсутності сортування можна припиняти.

Але виявляється, що і це вдосконалення такоя; можна по-кращити. Тому друге вдосконалення полягає в тому, щоб на кожному кроці запам'ятовувати номер елемента, з яким був виконаний останній обмін. Це означатиме, що всі елементи зище від цього місця уже впорядковані. Тому наступний пе­регляд можна виконувати лише до цього елемента.

Ці дві ідеї щодо покращення методу прямого обміну покла-іені в основу методу шейкерного сортування.

Розглянемо два приклади масивів і відсортуємо їх методом прямого обміну.

Приклад перший:

12,18, 42, 44, 55, 67, 94, 06.

У цьому прикладі «поганий» елемент (06) знаходиться на «важкому кінці». Він «спливе» на свое місце, тобто перему­титься на перше місце в масиві, за один прохід.

Приклад другий:

94, 06,12,18, 42, 44, 56, 67.

У цьому прикладі «поганий» елемент (94) на «легкому кін-ці». Він «потоне», тобто переміститься на останнє місце в ма-сиві, за сім проходів.

Метод прямого обміну можна вдосконалити так: чергувати напрям послідовних переглядів масиву. Тепер зрозуміло, чому пей метод носить назву «шейкерного» сортування.

Розглянемо цей метод на прикладі таблиці 18.

Таблиця18

159

У перших двох рядках таблиці будемо вказувати межі змі-ни індексів елементів масиву, який розглядається на даному кроді тдодо його апорядкування. Змінна L - індекс крайнього лівого елемента масиву, до якого міняється значения змінної ; при викошшні опорації a[j — 1] > a\j\, R — відповідно крайньо­го правого.

3 таблиці 18 видно, що на кожному кроці запам'ятовується порядковий елемент масиву, на якому було зроблено останній обмін, і це дає змогу значно зменшити кількість проходів маси­ву для отримання його остаточного відсортованого варіанта. Крім того, зміна напрямів сортування при кожному проході масиву також дає свої переваги.

Реалізащю описаного алгоритму можна представити у ви-гляді тексту такої Pascal-програми:

L := 2; R := n; k := п; repeat

for j := R downto L do if a[j-1]>a[j]then begin

| x := aU - 1]; aU - 1] := a[j]; afl] := x; k := j end; L := k + 1; for j := L to R do if a[j- 1] >a[j]then begin

| x := a[j - 1]; a[j - 1] := a[j]; aD] := x; k := j end; R:=k-1; until L > R;

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

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

У загальному випадку всі сортування фактично пересувають кожний елемент а. на кожному елементарному кроці на одну позипДю. Тому вони вимагають л² таких кроків.

Отже, можна говорити, що оцінка ефективності виконання будь-якого покращеного алгоритму сортування, так само як для прямих методів, становить 0(л²).

160

При тестуванні покращених алгоритмів сортування, як і для прямих методів, треба сформувати такі вхідні дані:

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

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

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

• елементи вхідного масиву розміщені випадковим чином. Коректність алгоритму перевірити при п = 10, п » 100,

п ■= 1000, п = 10 000, ті = 30 000.

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

1. На чому базується ідея покращення методу прямого включения?

2. Який пошуковий алгоритм застосовується для покращення ме­тоду прямого включения?

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

4. На чому базується ідея покращення методу прямого обміну?

5. Наведіть приклади послідовностей, які доводять ефективність чергування застосування методу прямого обміну від початку ма­сиву до кінця, і навпаки.

6. Сформулюйте алгоритм шейкерного сортування.

7. Продемонструйте у вигляді таблиц! роботу методу шейкерного сортування на конкретному масиві значень.

8. Запишіть текст Pascal-програми, який реалізує алгоритм шей­керного сортування.

9. Проанапізуйте ефективність роботи покращених методів сорту­вання.

10. Якою є оцінка ефективності роботи покращених методів сорту­вання?

Завдання

1. Реалізувати у вигляді програми алгоритм сортування за­дано! послідовності за зростанням методом з двійковим вклю­чениям.

2. Реалізувати у вигляді програми алгоритм шейкерного сортування заданої послідовності за зростанням.

3. Змінити алгоритми у завданнях 1-2 так, щоб сортування відбувалося за спаданиям.

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

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

6. Підібрати власні тести, які доводять переваги й показу-ють недоліки кожного з покращених методів сортування при п > 100.

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

в Іиформ.іпіки. 9 I" >•• I

161

УДОСКОНАЛЕНІ МЕТОДИ СОРТУВАННЯ

Сортування методом Шелла

Цей метод був запропонований Дональдом Л. Шеллом у 1959 р. Цей метод (ShellSort) дає змогу здійснювати сортування за допомогою включения з відстанями, що зменшуються, і ба-зується він на іде'і методу прямого включения.

Розглянемо відомий уже нам масив:

44, 55, 12, 42, 94, 18, 06, 67.

Спочатку впорядкуємо елементи, які знаходяться на відста-ні 4 один від одного (мал. 55).

41

55

12

42 94

Мал. 55

18

0G

G7

3 малюнка видно, що методом включения впорядковуються такі групи: 44 і 94, 55 і 18, 12 і 06, 42 і 67. У результаті вико-нання впорядкування в кожній групі отримаємо такі групи: 44 і 94, 18 і 55, 06 і 12, 42 і 67. Оскільки впорядкування відбу-валося на сво'їх місцях, то результатом його буде масив:

44, 18, 06, 42, 94, 55, 12, 67.

Тепер розглянемо групи елементів, що знаходяться на від-стані 2 один від одного. Такий крок обрано для того, щоб «за-хопити» результат попереднього обміну (мал. 56).

Мал. 56

Випишемо і в цьому разі ті групи елементів, які сортуються методом включения: перша - 44,06,94,12, друга -18,42,55,67. Застосувавши метод включения до кожної з них, отримаемо: першу - 06, 12, 44, 94; другу - 18, 42, 55, 67. У результаті маемо такий масив:

06,18,12,42,44,55,94,67.

Залишилося зробити останне впорядкування методом вклю­чения, утворюючи групи з кроком 1 (мал. 57).

162

06 18 12 42 44 55 94 67

Мал. 57

Тепер у результата застосування методу включения отри-маемо остаточний вигляд відсортованого масиву:

06,12,18, 42, 44, 55, 67, 94.

Зрозуміло, що у випадку поділу масиву на групи з кро-ком 1 ми насправді розглядаємо повністю сам масив, тобто від-бувається звичайне сортування. Але на ней момент масив уже майже відсортовано, тому, застосовуючи метод включения, зводимо до мінімуму кількість переставлень елементів масиву. Те саме можна сказати і про всі попередні кроки.

Тепер необхідно визначитися, яким чином найоптимальні-ше визначати кроки для поділу заданого масиву на групи. У ре­зультат! своїх досліджень Д. Кнут показав, що мае сенс вико-ристовувати такі послідовності кроків:

1) 1, 4, 13, 40, 121, ..., де h_h = ЗЛ, + 1;

2)l,8,7,15»31,...,flBft_t-2V_l+l.

Яким чином вибрати ту чи іншу залежність для кроків при

сортуванні методом Шелла? Можливо, це залежить від довжи-ни масиву: для невеличких масивів — перший варіант, для ве­ликих — другий. Хоча поняття «малий» і «великий» дуже від-носне.

Час уже навести текст програми мовою Pascal, що реалізує описаний алгоритм. Спочатку нагадаємо алгоритм, що відпові-дає методу прямого включения, і оформимо його у вигляді про-цедури:

procedure InsertionSort; varx, j: word; begin

x:=a[i];j:=i; while x < a[j - h] do begin

a[j]:=a[j-h]; j:=j-h end; a[j] := x end;

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

в*

163

частина алгоритму, що реалізує метод Шелла, виглядатиме так:

while h > = 1 do {Повторения алгоритму з наступним кроком л.}

begin

j:=1;i:=1;

while j <= n - h do {Визначення початкового елемента}

begin {кожної фупи з кроком л.}

і := і + h;

while і <= n do {Включения кожного елемента a[i]}

begin {у попередню частину визначеної групп з кроком л.}

InsertionSort; inc(i, h) end; inc(j);i:=j; end;

{Перерахунок кроку л за визначеним алгоритмом} h := (h - 1) div 3; {або h •= (h - 1) div 2.)

end;

Для того щоб визначити початкове значения величини Л, яке містить значения максимального кроку поділу заданого масиву на групи, можна запропонувати такий алгоритм: бу-демо збільшувати значения h за формулою h_k = 3A_k_, + 1 або h_h ■ 2/»j_j + 1 доти, доки воно не перевершить кількості елемен-тів масиву п:

h_new := 1; while h_new <= n do begin

h_old := h_new; h_new := 3 * h_old + 1; end; h:=h_old;

Однак тестування наведеного варіанта алгоритму, що реалі-зує метод Шелла, показали не дуже втішні результати. Для ве­ликих п вони виявилися значно гіршими, ніж у наступних удосконалених методах, які розглянемо далі.

У своїй праці Н. Вірт розглядає питания методів сортування та пропонуе алгоритм сортування масиву методом Шелла з ви-користанням так званих бар'єрів. Це аналогія використання змінної а₀ в алгоритмі прямого сортування методом включен­ия, який відіграє роль бар'ера при включенні елемента а. у під-послідовність Oj ... a_t__v Оскільки сортування методом вклю­чения з відстанями, що зменшуються, використовує під час сортування різні підпослідовності з кроком h, то й необхідно для кожної такої групи використовувати відповідно свій бар'єрний елемент. Для цього резервуються елементи у масиві

164

а[ - h_max..n]. Наведемо текст Pascal-процедури, що безпосе-редньо реалізує цей варіант алгоритму включения:

procedure InsertionSort; var m: word; x: word; begin

x := a[i]; m := i-k; if s = 0 then s := - k; inc(s); a[s] :=x; while x < a[m] do begin a[m + k] :=a[m]; m := m - k end; a[m + k] := x end;

Для обчислення кроків, які використовуються для визна-чення підпослідовностей, де відбувається сортування включен­иям, використовується масив h. Для л = 20 000 він міститиме 9 елементів, а для п = 30 000 - усього 10. Значения елементів цього масиву можуть описуватися типом word. Частина основ-ної програми, що реалізує алгоритм методу Шелла з бар'єрами, виглядатиме так:

h_new := 1; count := 0; while h new <= n do begin

inc(count); h_old := h_new; h_new := 3 * h_old + 1; end; h[1]:=h_old; for i := 2 to count do

h[i]:=(h[i-1]-1)div3; forj := 1 to count do begin

k:=h[j];s:=-k; for i := k + 1 to n do InsertionSort; end;

Повний аналіз сортування методом Шелла дуже складний і доводиться на рівні математичного аналізу. Саме так Д. Кнут до-вів, що в найгіршому випадку при обраних значениях кроку я складність алгоритму становить 0(л^3/2), а при виборі залежності кроку h_k = 2h_k_, + 1 - 0(п^6/5). Зрозуміло, що це краще, ніж 0(п²).

Тестування алгоритму, що реалізує метод Шелла, треба провести на таких вхідних даних:

165

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

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

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

• елементи вхідного масиву розміщені випадковим чином. При цьому передбачити різні за довжиною масиви: п = 10,

п = 100, п = 1000, п = 10 000, п = 30 000.

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

1. На якому методі базується сортування методом Шелла?

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

3. Наведіть приклад масиву та продемонструйте схематично ро­боту алгоритму сортування методом Шелла.

4. За якими алгоритмами Д. Кнут запропонував визначати кроки для поділу заданого масиву на групи гид час сортування?

5. Запишіть у вигляді процедури мовою Pascal фрагмент алго­ритму сортування масиву методом прямого включения.

6. Запишіть алгоритм сортування масиву методом Шелла у вигля-ді тексту Pascal-програми. Прокоментуйте роботу окремих бло-ків цього алгоритму.

7. За яким алгоритмом можна визначити максимальне значения h кроку поділу масиву, що складається з п елементів?

8. Якою є оцінка ефективності роботи алгоритму сортування маси­ву методом Шелла?