Курсовая работа: Порівняльний аналіз ефективності та складності швидких алгоритмів сортування масивів

for j:=1 to N-i do

if a[j]>a[j+1] then begin x:=a[j]; a[j]:=a[j+1]; a[j+1]:=x end

End;

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

1) фіксувати, чи були перестановки в процесі деякого етапу. Якщо ні, то - кінець алгоритму ;

2) фіксувати крім факту обміну ще і положення (індекс) останнього обміну. Очевидно, що всі елементи перед ним або після нього відповідно для сортування "бульбашкою" або "камінцем" будуть впорядковані ;

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

Читачу пропонується самостійно модифікувати наведені вище процедури з врахуванням цих покращень.

Аналіз прямого обміну. Розглянемо спочатку чисту "бульбашку". Для "камінця" оцінки будуть такими ж самими. Зрозуміло, що кількість порівнянь ключів C_i на i -ому проході не залежить від початкового розміщення елементів і дорівнює N-i . Таким чином

Кількість же перестановок залежить від стартової впорядкованості масиву. В найкращому випадку початково впорядкованогомасиву M_i =0 ; в найгіршому випадку зворотньо впорядкованогомасиву M_i =C_i *3; для довільного масиву рівноймовірно можливе значення M_i =C_i *3/2. Тому для оцінки ефективності алгоритму по перестановках можна скористатися наступними співвідношеннями:

;

;

.

Очевидно, що і цей алгоритм, аналогічно з іншими прямими методами, описує процес стійкого сортування.

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

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

Розділ ІІ. Швидкі методи сортування масивів

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

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

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

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

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

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

44 55 12 42 94 18 06 67

етап I-сортування

44 18 06 42 94 55 12 67

етап II-сортування

06 18 12 42 44 55 94 67