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

Параметри, за якими проводиться оцінка алгоритмів:

1. Час впорядкування–основний параметр, що характеризує швидкодію алгоритму.

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

3. Стійкість–стійка впорядкуванняне змінює взаємного розташування рівних елементів. Така властивість може бути дуже корисним, якщо вони складаються з декількох полів, як на рис. 1, а впорядкуваннявідбувається по одному з них, наприклад, по x.

Взаємне розташування рівних елементів з ключем 1 і додатковими полями " a ", " b ", " c " залишилося колишнім: елемент з полем " a ", потім –з " b ", потім –з " c ".

Взаємне розташування рівних елементів з ключем 1 і додатковими полями "a ", " b ", " c" змінилося.

4. Природність поведінки–ефективність методу при обробці вже відсортованих, або частково відсортованих даних. Алгоритм поводиться природно, якщо враховує цю характеристику вхідної послідовності і працює краще.

Обчислення часу виконання програм

Для того, щоб знайти час виконання програми, потрібно використати функцію clock(). Прототип функції clock()знаходиться в заголовковому файлі <ctime>, який потрібно підключити на початку програми. Функція clock() повертає значення часу в мілісекундах (1с = 1000млс). Причому відлік часу починається з момента запуску програми. Якщо потрібно виміряти час виконання всієї програми, то в кінці програми, перед оператором return 0; потрібно запустити функцію clock(), яка покаже робочий час. Для пошуку часу виконання фрагмента коду потрібно знайти різницю між початковим та кінцевим часом.

Завдання для виконання:

Провести порівняльний аналіз алгоритмів сортування, запропонованих у таблиці. Час виконання виміряти для різної кількості елементів одновимірного масиву: 10*N, 100*N, 10000*N. Дані записати в таблицю. (Для вимірювання часу виконання використати засоби мови програмування, вказати тип операційну систему та тип процесора).