39. Швидкі алгоритми сортування масивів.

Сортування включенням із зменшуваними відстаннями - алгоритм Шелла (1959)

Шелл запропонував проводити послідовне впорядкування підмасивів з елементів, які знаходяться на великих відстанях. При цьому на кожному наступному етапі відстані між елементами в групах мають зменшуватися.

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

1. на першому етапі окремо групуються і сортуються елементи, розміщені на відстані . Це є впорядкування підмасивів по 2 елементи, яке називатимемо N/2-сортування.

2. на другому етапі виконується впорядкування підмасивів по 4 елементи на відстані - -сортування і т.д.

На останньому етапі виконується одинарне сортування (впорядкування на відстані 1). Наприклад :

Кількість етапів сортування t як і відстані на кожному з них можна вибирати довільно. Зокрема, це може буди кількість цілочисельних поділів числа N на 2. тобто t=[log(N)].

Аналіз алгоритму Шелла. Поки що не має чітко обґрунтованих виборів відстаней, які давали б найкращу ефективність. Запропонований вище варіант вибору відстаней по степенях двійки із зменшенням вдвічі на кожному черговому етапі не є оптимальним. Адже при цьому на всіх етапах окрім останнього будуть порівнюватися та перегруповуватися окремо елементи лише із непарними індексними номерами та окремо елементи лише із парними номерами :

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

Сортування обміном на великих відстанях - алгоритм Quick Sort

Природно попробувати пришвидшити процес сортування сусідніх пар, порівнюючи пари елементів, що знаходяться далеко один від одного в масиві. К. Хоор розробив алгоритм Quick Sort із середнім часом роботи порядку . Припустимо, що перший елемент масиву, що сортується, є хорошим наближенням елемента, який вкінці опиниться на своєму місці у відсортованій послідовності. Приймемо його значення в якості ведучого елемента, відносно якого ключі будуть мінятися місцями.

44. Поняття програми. Програмування як процес розробки алгоритмів. Загальні підходи програмування.

Мова, на якій записується алгоритм для виконання на ЕОМ, називається мовою програмування. Програма - це алгоритм, записаний на мові програмування. Мова програмування належить до формальних мов.

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

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

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

Щоб виконати програму, написану на мові високого рівня, необхідно кожен оператор цієї програми перетворити у послідовність машинних команд.

Існує два різних методи виконання програми, написаної на мові високого рівня. В першому із цих методів спеціальна службова програма, називається компілятором, спочатку переводить всі оператори вихідної програми на машинну мову, а тоді отримана машинна програма виконується комп'ютером. При другому методі використовується інша службова програма, яка називається інтерпретатором. Інтерпретатор послідовно переводить оператори вихідної програми на машинну мову, і комп'ютер відразу їх виконує.

І компілятор, і інтерпретатор самі являються програмами на мові машини. Використання кожного із них має свої переваги і недоліки. Компілятор переводить програму на машинну мову як одне ціле, перевіряючи не тільки правильність окремих операторів, але і взаємодію їх між собою. Інтерпретатор набагато кращий у використанні. Він дозволяє почати виконання навіть не повністю закінченої програми. Але інтерпретатор не може перевірити взаємодію всіх частин програми. Зазвичай, у режимі інтерпретації виконуються програми на мові Бейсік, а для більшості інших мов програмування використовується компіляція програм.

Таким чином, виконувачем програми на мові високого рівня являється не один комп'ютер, а сукупність комп'ютерів і спеціальних програм. Такі програми являються оболонкою, "верхнім одягом" комп'ютера. Ці програмні оболонки дозволяють підвищити рівень комп'ютера як виконувача алгоритмів і приховати від користувача складні і непотрібні йому дрібниці роботи апаратури комп'ютера. Сукупність мовних і програмних засобів для розробки і виконання програм називається системою програмування.

При перекладі програм з навчальної алгоритмічної мови в основному не виникає складності, оскільки всі мови розробляються по давно визначеним алгоритмам і структурам. Існують лише незначні відхилення.

Приклад:

Алгоритмічна мова

Алг піраміда

дійсн x, k, r, m, f, s1, s2, s3, s4, пл

поч

ввести x, k, r, m, f

площа (x, k, r, s1)

площа (x, r, m, s2)

площа (x, m, f, s3)

площа (x, f, k, s4)

пл:=s1+s2+s3+s4+ x*x

вивести пл

кін

Паскаль

Program Piramida;

var X, K, R, M, F, S1, S2, S3, S4: Real;

procedure pl(A, B, C: Real; var S:Real;);

var P:Real;

begin

P:=(A+B+C)/2;

S:=Sqrt(P*(P-A)*(P-B)*(P-C));

end;

Begin

Read(X, K, R, M, F);

Pl(X, K, R, M, F);

Pl(X, K, R, S1);

Pl(X, R, M, S2);

Pl(X, M, F, S3);

Pl(X, F, K, S4);

Write(S1+S2+S3+S4+X*X);

end.

Для зручності реалізації алгоритму використаємо два вказівники І, J, перший з яких вестиме відлік вздовж розглядуваної частини масиву зліва, а друтий - справа. Початково їх значення будуть відповідно 1=1, J=N. Таким чином ведучим елементом буде значення а[І]. Перестановки ключів проводяться за такими принципами :

1) порівнюються елементи а[І] та a[J]; якщо , то здійснюється крок вліво J:=J-1; і порівняння повторюється; зменшення J продовжується доти, поки не виконається умова а[І]> a[J];

2. якщо при порівнянні елементів досягнута умова а[І]> a[J], то проводиться обмін місцями ключів а[І] та a[J] і здійснюється крок вправо І:=І+1; таким чином ведучий елемент перейшов в позицію J; порівняння ключів із збільшенням І продовжується доти, поки знову не виконається умова а[І]> a[J];

3. у випадку виконання умови а[І]> a[J] проводиться обмін місцями ключів а[І] та a[J] і здійснюється крок вліво J:=J-1; при цьому ведучий елемент знову повертається в позицію І.

Цей процес із почерговим зменшенням J та збільшенням І повторюється з обох кінців послідовності до "середини" до тих пір, поки не досягнеться I=J.

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

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

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

Сортування вибором при допомозі дерева - алгоритм Heap Sort.

Прямий вибір - повторюваний пошук найменшого елемента серед N елементів, N-1 елементів, N-2 і т.д. Кількість порівнянь при цьому (N2-N)/2. Для підвищення ефективності необхідно залишати після кожного етапу побільше інформації окрім ідентифікації найменшого ключа.

Після N/2 порівнянь можна знайти в кожній парі елементів найменший, після N/4 порівнянь - менший із пари вже вибраних на попередньому кроці і т.д. Виконавши загалом N/2+N/4+...+2+l=N-l порівнянь, можна побудувати дерево вибору та ідентифікувати його корінь як шуканий найменший елемент. Наприклад. На наступному етапі сортування проводиться рух вздовж віток, які відмічені мінімальними елементом, і вилучення його з дерева шляхом заміни на пустий елемент.

Далі здійснюється заповнення "дірок" у дереві. На першому рівні залишається "дірка" від вилученого елемента, а на наступних знову вибирається менший із двох сусідніх попереднього рівня. "Дірка" при порівнянні вважається як завгодно великим значенням.

Елемент, що опинився в корені - знову найменший. Після N таких кроків дерево стане пустим, в ньому будуть лише одні "дірки" (сортування закінчене). На кожному з N етапів виконується log(N) порівнянь. Тому на весь процес впорядкування потрібно порядку N*log(N) операцій плюс N-1 операцій для побудови дерева

Тому можна вважати, що розглядуваний метод як і по порівняннях так і по перестановках має ефективність порядку .

for j:=I downto R+1 do a[j]:=a[j-1] end end;

Сортування прямим вибором. На відміну від включення, коли для чергового елемента відшукувалося відповідне місце в «готовій» послідовності, в основу цього методу покладено вибір відповідного елемента для певної позиції в масиві. Цей прийом базується на таких принципах:

1) на і-ому етапі серед елементів а₁, а₂,...а_N вибирається елемент з найменшим ключем a_min;

2) проводиться обмін місцями а_min та а₁.

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

Такий алгоритм можна записати у вигляді послідовності команд :

for i:=1 to N-1 do

begin

k:=номер_найменшого_ключа_серед а[і],...,a[N]; обмін місцями a[k] та а[і] end;

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

Procedure Straight_Selection;

var i,j,k:integer; x:basetype;

Begin for i:=1 to N-1 do begin k:=1; for j:=i+1 to N do

if a[j]<a[k] then k:=j; x:=a[k]; a[k]:=a[i]; a[i]:=x end end;

Сортування прямим обміном. Даний метод базується на повторенні етапів порівняння сусідніх ключів при русі вздовж масиву. Якщо наступний елемент виявиться меншим від попереднього, то відбувається обмін (звідси і назва методу). Таким чином, при русі з права наліво за один етап найменший ключ переноситься на початок масиву. Зрозуміло, що кожен наступний прохід можна закінчувати після позиції знайденого на попередньому етапі мінімального елемента, оскільки всі елементи перед ним вже впорядковані. Розглядуваний процес дещо нагадує виштовхування силою Архімеда бульбашки повітря у воді. Тому цей алгоритм ще називають "бульбашковим" сортуванням.

Програмна реалізація методу прямого обміну або "бульбашки" матиме вигляд процедури:

Procedure Buble_Sort;

var i,j:integer; x:basetype;

Begin

for i:=2 to N do

for j:=N downto i do

if a[j-1]>a[j] then

begin x:=a[j]; a[j]:=a[j-1]; a[j-1]:=x end end;

Якщо етапи порівняння та обміну проводити зліва направо, то відбуватиметься виштовхування найбільшого елемента в кінець масиву. Очевидно такий процес відповідає опусканню під дією сили тяжіння камінця у воді. Назвемо цей алгоритм "камінцевим" сортуванням:

Procedure Stone_Sort;

var i,j:integer; x:basetype;

Begin for i:=1 to N-1 do

for j:=1 to N-i do

if a[j-1]>a[j] then

begin x:=a[j]; a[j]:=a[j-1]; a[j-1]:=x end end;

1 1 1 3

1 1 1 3

1 1 1 3 - Вихід образу за межі бази.

Але при даному методі визначається дефект КМП. Він проявляться, коли:

• на початку образу мають місце повторення однакових елементів,

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

• Кількість повторень у базі неповинна бути кротною кількості повторень у образі.

Програмна реалізація алгоритму Кнута-Моріса-Пратта:

Begin

i:=1; j:=1; k:=1;

while (i<=N-M+1) and (j<=M)do

Begin

j:=1;

While(j<=M) and (a[k]=b[j] ) do

Begin

j:=j+1;

k:=k+1;

end;

if k=I then i:=i+1

ekse k:=i;

End;

If j>M then writeln (‘There is such element with index ’, i-j)

Else writeln (‘there is no such element’)

End.