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

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

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

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

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

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

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

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

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

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

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