2015-09-06
918
В загальному алгоритм швидкого сортування можна описати так:
quickSort
· Вибрати опорний елемент p
· Розділити масив по цьому елементу (реорганізувати масив таким чином, щоб всі елементи, менші або рівні опорному, виявилися зліва від нього, а всі елементи, більші опорного, - справа від нього)
· Якщо підмасив зліва від p містить більше одного елемента, викликати quickSort для нього (тобто повторити рекурсивно для підмасиву зліва від р)
· Якщо підмасив справа від p містить більше одного елемента, викликати quickSort для нього (тобто повторити рекурсивно для підмасиву справа від р)
Часто в якості опорного елемента пропонується вибрати медіану (середину масиву). Однак можна підібрати приклад, при якому алгоритм з вибором медіани в якості опорного елемента буде видавати неправильну відповідь. Відомі стратегії: вибирати постійно один і той самий елемент, наприклад, перший або останній; вибрати елемент випадковим чином.
Недолік вибору в якості опорного одного із крайніх елементів масиву — при передачі параметром уже відсортованого масиву такий вибір призводить до найгіршого випадку.
Недолік вибору опорного елемента випадковим чином — залежність швидкості алгоритму від реалізації генератора псевдовипадкових чисел. Якщо генератор працює повільно і видає погані послідовності псевдовипадкових чисел, можлива затримка роботи алгоритму.
Оцінювання середньостатистичних значень M та C є нелегкою задачею з огляду на необхідність використання апарату теорії ймовірностей, але обидві величини будуть порядку
~ N log 2 N.
Постановна задачі
1. Написати програму, що реалізує один з простих методів сортування (згідно з номером варіанту).
2. Написати програму, що реалізує метод Шелла або швидкого соpтування (згідно з номером варіанту).
3. Згенерувати три масиви з випадковими елементами типу іnt довжиною 100, 1000 та 10000 елементів, відповідно.
4. Відсортувати одержані масиви за збільшенням елементів, визначивши при цьому такі параметри:
o кількість порівнянь;
o кількість обмінів;
o фактичний час роботи,
