Лабораторна робота № 7

Тема: сортування.

Мета: закріпити теоретичні знання та набути практичний досвид впорядкування набору статичних та динамічних структур даних.

Теми для попередньої роботи:

• масиви та списки;

• алгоритми пошуку;

• класифікація алгоритмів сортування;

• алгоритми сортування.

Загальні відомості

Алгоритми сортування характеризуються порядком (ступеневі - O(Na), лінійні - O(N) або логарифмічні - O(loga(N)), вимогами до ресурса пам’яті, чутливістю до упорядкованості вхідного набору даних, складністю.

Класифікація алгоритмів сортування за логічними характеристиками. Виділяють чотири групи алгоритмів сортування.

1. Сортування вибіркою. Із вхідної множини вибирається наступний за критерієм упорядкованості елемент і включається у вихідну множину на наступне за номером місце (сортування простою вибіркою, обмінне сортування простою вибіркою, обмінне сортування простою вибіркою з пошуком мах і mіn, бульбашкове сортування класичне, бульбашкове сортування з ознакою, бульбашкове сортування із запам’ятовуванням місця останньої перестановки, Шейкер-сортування, сортування Шелла).

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

3. Сортування розподілом. Вхідна множина розбивається на ряд підмножин (можливо, меншого обсягу) і сортування проводиться усередині кожної такої підмножини (порозрядне цифрове сортування, швидке сортування Хоара, «Кишенькове» сортування).

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

Типове завдання

Розробити програму сортування масиву цілих чисел згідно із алгоритмом Шейкера.

Текст програми

#include<iostream>

#include<conio.h>

using namespace std;

#define N 20 //кількість елементів у масиві

int a[N]; //масив, вміст якого буде впорядковуватися

void Create()

{

int i;

for(i=0; i<N; i++)

a[i]=rand() % 100;

}

void Vivod()

{

int i;

for(i=0; i<N; i++)

cout << " " << a[i];

cout << "\n";

}

void Sort()

{

int i,j,t;

int key=0; // key – ключ, дорівнює 1, якщо не було перестановок(масив відсортований)

for (i=1; i<N-1;i++)

{

if (key) break;

key=1;

for (j=i; j<N-i;j++)

if (a[j-1]>a[j])

{

key=0;

t=a[j-1]; a[j-1]=a[j]; a[j]=t;

}

for (; i; i--)

if (a[j]<a[j-1])

{

key=0;

t=a[j]; a[j]=a[j-1]; a[j-1]=t;

}

}

}

void main()

{ system("chcp 1251 > nul"); // для роботи з кирилицей

Create();

cout << "Исходный массив \n";

Vivod();

Sort();

cout << "Отсортированный массив \n";

Vivod();

getch();

}

Результат роботи програми

Исходный массив

41 67 34 0 69 24 78 58 62 64 5 45 81 27 61 91 95 42 27 36

Отсортированный массив

0 5 24 27 27 34 36 41 42 45 58 61 62 64 67 69 78 81 91 95

Для продолжения нажмите любую клавишу . . .

Індивідуальні завдання

Написати програму, що реалізує сортування статичного та/або динамічного набору даних заданим способом згідно даних табл. 7.1. Визначити кількість порівнянь та обмінів для наборів даних, що містять різне число елементів (20, 1000, 5000, 10000, 50000). Оцінити час сортування. Дослідити вплив початкової впорядкованості набору даних (відсортований, відсортований у зворотному порядку, випадковий). Всі отримані дані записати в таблицю 7.2. Зробити висновки.

Таблиця 7.1 – Варіанти індивідуальних завдань

N	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
Номер алгоритму сортування	13	1 10	12	3 7	11	4 8	10	5 9	9	6 2	8	7 4	7	8 1	6	9 13	5	2 3	4	11 13	3	10 6	2

Примітка:

1. Для непарного N реалізувати вказаний алгоритм сортування на статичному та динамічному наборах даних.

2. Для парного N реалізувати два алгоритми сортування на одному з наборів даних (статичному або динамічному).

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

Алгоритми сортувань

1. Пірамідальне сортування.

2. Модифікація бульбашкового сортування з ознакою.

3. Бульбашкове сортування з запам'ятовуванням місця останньої перестановки.

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

5. Сортування Шелла.

6. Сортування двійковими вставками.

7. Бульбашкове сортування вставками.

8. Турнірне сортування.

9. Сортування простою виборкою.

10. Сортування Хоара.

11. Сортування вибором (пошук min та max в одному проході).

12. Порозрядне цифрове сортування.

13. Сортування попарним злиттям.

Таблиця 7.2 - Порівняльна таблиця ефективності алгоритму

Відсортований набір даних	20	1000	5000	10000	50000
Кількість порівнять
Кількість пересилань
Час сортування
Відсортований в обратному порядку	20	1000	5000	10000	50000
Кількість порівнять
Кількість пересилань
Час сортування
Випадковий набір даних	20	1000	5000	10000	50000
Кількість порівнять
Кількість пересилань
Час сортування

Контрольні питання

1. Назвіть всі алгоритми сортування порядку O(n²), O(n), O(log(n)).

2. Назвіть всі алгоритми сортувань, що відносяться до групи бульбашкових. Чим характеризуються ці алгоритми?

3. Вкажіть всі можливі модифікації алгоритму сортування Шейкера. Напишіть одну з вказаних процедур Шейкер – сортування.

4. В алгоритмі сортування Шелла шаг d визначається як N % 2. А чи можна визначати d інакше, чому запропоновано саме такий алгоритм?

5. В чому основна ідея алгоритму сортування Хоара?

6. Чим пояснюється наявність такої кількості алгоритмів сортування?

7. Поясніть, чому алгоритми сортувань на деревах характеризуються порядком log₂(N)?

8. Назвіть відомі вам алгоритми сортувань, час виконання яких не залежить від стану впорядкованості вхідного масиву.

9. За логікою роботи на які групи поділяють всі алгоритми сортувань?

10. Назвіть алгоритми сортівання, які чутливі до ступеня впорядкованості вхіного набору даних.

11. Чи існують алгоритми сортування, в яких немає порівнянь елементів набору даних, що впорядковується?