МЕТОДИ СОРТУВАННЯ МАСИВІВ

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

Бібліотеку "Geometry" замовнику спихнули, гроші отримали, гуляли всією командою. Не дай, Боже, так напиватися надалі... Але пристойна хвірма без роботи не сидить! Аж ось і нове замовлення.

Оце для Вовчика було справжньою несподіванкою: виявляється, амерікоси цікавляться не тільки конкретними програмами, але й дослідницькими роботами!

Нам запропоновано дослідити якість роботи методів сортування масивів. Методів сортування — безліч. Всі вони відрізняються одне від одного силою критеріїв. І для кожного з методів можна вибрати критерій, за яким він буде найкращим серед інших. На великих масивах найшвидшим вважається метод швидкого сортування (а ви як думали?) QuickSort. Серед початківців найкращім вважається бульбашковий метод простого обміну BubbleSort (не плутати з Bubble gum). Бо найпростіший — один подвійний цикл, і все. А ще ж є метод включення, вибору, двійкового сортування, шейкерного, їхні численні модифікації...

Методи описано у конспекті лекцій та багатьох книжках. До групи т. зв. простих відносимо методи простого включення, вибору та обміну ("бульбашковий"), до групи більш довершених - методи Шелла, пірамідального, швидкого сортування та сортування злиттям.

Серед критеріїв, за якими порівнюються методи, розрізнюють:

• C (від compare) - кількість порівнянь ключів між собою;
• M (від move) - кількість операцій перезапису елементів з місця на місце у оперативній пам'яті або кількість обмінів;
• T (від time) - загальний час роботи процедури.

1. Написати програму, що реалізує один з простих методів сортування (за варіантом). Для одного з довершених методів припустимо скористатися готовою програмою. Програми мають бути написані одною мовою програмування. Пpоцедуpи соpтування методами Шелла, пірамідального та швидкого соpтування мiстяться у файлах мовою С++ та Паскаль, вiдповiдно.
2. Згенерувати три масиви з випадковими елементами довжиною 100, 10000 та 100 000 елементів, відповідно.
3. Відсортувати одержані масиви за збільшенням елементів, визначивши при цьому такі параметри:
   • кількість порівнянь;
   • кількість обмінів;
   • фактичний час роботи,
   необхідні кожній з програм (простий та один з довершених методів), щоби відсортувати кожен з трьох масивів. Швидкодія сучасних ЕОМ може привести до того, що час роботи процедури буде дорівнювати нулеві з точністю, яку забезпечує системний таймер. Тоді варто запустити її багато разів у циклі, а потім усереднити результат.
4. Оформити звіт, навівши одержані експериментальні дані та теоретичні оцінки у вигляді таблиць.

1. текст програми, яку Ви написали;
2. надрукований масив на 100 елементів до сортування та після нього (чи взагалі сортує?);
3. теоретичні оцінки для кількостей операцій для методів Вашого варіанту;
4. результати експериментального дослідження та - обов'язково - їхній аналіз.

Останнi два пункти можна викласти, наприклад, у такiй таблицi:

Номер варіанту обчислюється як ((N_сп-1) mod 12) + 1, де N_сп - Ваш номер у журнальному списку.