11. Аналіз алгоритмів на основі прямого обміну.

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

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

;

;

.

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

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

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

12. Блок-схеми процедур

1) Блок-схема процедури сортування методом прямим включенням (вставкою):

2) Блок-схема процедури сортування методом бульбашки:

13. Опис програми

Ім’я – Sortirovka.

Глобальні константі:

• const N=100;

• const punkt;

Типи користувача:

• seq=array[0..N] of integer;

• array[1..7] of string[50]

Глобальні змінні:

• ii,y : byte

• klav: char;

• kr,ks,t2,t:integer;

• b,p,NN,NA: integer;

• f_n:string;

• f:text;

• mas,mas_p,mas_b:seq;

• x,x1,x2:seq;

• ch:char;

Призначення – виводить на екран текстове меню яке виконує діалог з користувачем.

Опис процедур і функцій:

1. procedure Init_Mas

Локальні змінні:

- a,b,c:seq

- i:integer

Ініціалізує масив( тобто створює його ).

2) procedure OutCrnt

Виводить на екран результати.

3) procedure Sort_Pryam

Локальні змінні:

- a:seq; b:integer

- i,j,x:integer

Сортує масив методом прямого включення.

4) procedure Buble_Sort

Локальні змінні:

- a:seq; b:integer

- i,j,x:integer

Сортує масив методом прямого включення.

5) procedure Print_mas

Локальні змінні:

- a:seq

- i:integer

Виводить на екран даний масив.

6) procedure save

Локальні змінні:

- a:seq

- i,j:integer

Зберігає дані результати програмі у файл.

7) procedure MENU

Забезпечує виведення на екран пунктів та зручне користування для користувача.

14. Структура вхідних і вихідних файлів

Вхідні дані:

Вводимо масив розмірність якого 100 елементів…

ne sort:

38 25 27 21 43 37 11 21 41 49 1 23 21 34 16 35 2 37

32 42 24 16 8 30 49 13 0 0 9 18 38 41 9 0 47 47

49 2 20 25 4 44 2 7 41 6 5 20 47 10

Далі програма має його відсортувати методами які вказані у меню і вивести на екран результати з кількістю перестановок.

Вихідні дані:

Виводимо результати даного масива, який вже відсортований методами сортування з кількістю перестановок…

sort pryam:

kilkist perestanovok:

49

0 0 0 1 2 2 2 4 5 6 7 8 9 9 10 11 13 16

16 18 20 20 21 21 21 23 24 25 25 27 30 32 34 35 37 37

38 38 41 41 41 42 43 44 47 47 47 49 49 49

sort bulka:

kilkist perestanovok:

671

0 0 0 1 2 2 2 4 5 6 7 8 9 9 10 11 13 16

16 18 20 20 21 21 21 23 24 25 25 27 30 32 34 35 37 37

38 38 41 41 41 42 43 44 47 47 47 49 49 49

Тут можна побачити який з даних методів сортує краще.