9.1.4. Порівняння ефективності алгоритмів сортування

Ефективність того або іншого алгоритму сортування оцінюється інтегральним показником – тривалістю виконання сортування. Основними операціями, на які затрачається машинний час, є порівняння й пересилання.

Операція порівняння (наприклад, типу a[j+1]>a[j]) – один з основних гальмуючих факторів, особливо, якщо виконується сортування рядків. Наприклад, для з'ясування, який із двох схожих рядків більше, доводиться порівнювати букву за буквою на великій довжині рядка. При роботі з числовими масивами одна операція порівняння виконується значно швидше, ніж при порівнянні рядків. Однак загальне число порівнянь у процесі сортування росте пропорційно квадрату розміру масиву. Можна показати, що робота кожного з розглянутих методів сортування (обміну, вибору й вставок) характеризуються приблизно однаковим числом порівнянь , де – розмір масиву.

Оскільки по числу порівнянь розглянуті три методи сортування майже рівноцінні, порівняльну ефективність методів потрібно визначати по числу пересилань. До пересилань ставляться операції присвоювання (наприклад, для перестановки двох елементів масиву за допомогою функції swap потрібно виконати три пересилання). Число пересилань у наведені вище функціях сортування зберігається в змінної mov (див. пункти 9.1.1 – 9.1.3).

9.1.5. Генерація псевдовипадкових чисел

Функція rand()%max при заданому параметрі max фактично генерує одне ж і ту послідовність випадкових чисел. Щоб при кожному запуску генератора породжувалася нова послідовність псевдовипадкових чисел, потрібно використати функцію srand, що встановлює точку відліку при генерації чисел і ставиться перед функцією rand, наприклад,

#include <stdlib.h>

#include <time.h>

. . .

srand((unsigned)time(NULL));

for (int i=0; i<n; i++)

a[i] = rand()%max;

9.2. Постановка задачі

Скласти програму для сортування масиву випадкових чисел трьома методами: обміну, вибору й включень. Проаналізувати ефективність різних методів сортування.

9.3. Методичні вказівки

1. Програма повинна мати наступну структуру:

<Підключення необхідних бібліотек>

<Ініціалізація змінних>

<Цикл по розміру масиві>

<Створення i ініціалізація дінамичного масиву >

<Печатка вихідного масиву>

<Копіювання вихідного масиву>

<Сортування копії масиву методом Buble>

<Сортування копії масиву методом Selection>

<Сортування копії масиву методом Insertion>

<Виведення результатів сортування>

Операції ініціалізації, виведення, сортування масиву мають бути реалізовані за допомогою функцій.

2. На етапі налагодження програми показувати на екрані вихідний масив і результаті ітерації. Потім при відображенні результатів сортування (див. наступний пункт) відключити це виведення.

3. Результати сортування різними методами (кількість пересилань) потрібно вивести у вигляді таблиць:

num Buble Select Insert

..... ...... ...... ......

..... ...... ...... ......

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

5. На основі отриманих даних побудувати в електронних таблицях Excel графіки залежностей середньо арифметичного числа пересилань від розміру масиву для трьох методів. По осі абсцис – значення num , по осі ординат – відношення mov/num.

9.4. Зміст звіту