Інструкція користувача.
Порівняння загальних характеристик роботи різних методів сортування
Вибирати опорним елементом середній з трьох (першого, середнього і останнього елементів). Такий вибір також спрямований проти гіршого випадку. програма visual метод сортування Щоб уникнути досягнення небезпечної глибини рекурсії в гіршому випадку (або при наближенні до нього) можлива модифікація алгоритму, що усуває одну гілку рекурсії: замість того, щоб після поділу масиву викликати рекурсивну… Читати ще >
Інструкція користувача. Порівняння загальних характеристик роботи різних методів сортування (реферат, курсова, диплом, контрольна)
Сортування методом Шелла
У 1959 році Д. Л. Шелл запропонував замість систематичного включення елемента з індексом i в підмасив попередніх йому елементів (цей спосіб суперечить принципу «балансування», чому і не дозволяє отримати ефективний алгоритм) включати цей елемент в підсписок, що містить елементи з індексами ih, i-2h, i-3h і т.д., де h — деяка натуральна постійна. Таким чином формується масив, в якому h-серії елементів, віддалених один від одного на відстань h, сортуються окремо:
Після того, як розсортовані непересічні h-серії, процес поновлюється з новим значенням h '.
Доведено, що максимальна складність алгоритму Шелла становить O (n5 / 4). Так як.
(3.1).
то цей вид сортування придатний для послідовностей, що мають приблизно до 70 тис. елементів.
Покращення
При виборі опорного елемента з даного діапазону випадковим чином гірший випадок стає дуже малоймовірним і очікуваний час виконання алгоритму сортування — O (n lg n).
Вибирати опорним елементом середній з трьох (першого, середнього і останнього елементів). Такий вибір також спрямований проти гіршого випадку. програма visual метод сортування Щоб уникнути досягнення небезпечної глибини рекурсії в гіршому випадку (або при наближенні до нього) можлива модифікація алгоритму, що усуває одну гілку рекурсії: замість того, щоб після поділу масиву викликати рекурсивну процедуру поділу для обох знайдених підмасива, рекурсивний виклик робиться тільки для меншого підмасива, а більший обробляється в циклі в межах цього ж виклику процедури. З точки зору ефективності в середньому разі різниці практично немає: накладні витрати на додатковий рекурсивний виклик і на організацію порівняння довжин підмасива і циклу — приблизно одного порядку. Зате глибина рекурсії ні за яких обставин не перевищить log2n, а в гіршому випадку виродженого поділу вона взагалі буде не більше 2 — вся обробка пройде в циклі першого рівня рекурсії.
Розбивати масив не на дві, а на три частини (див. Dual Pivot Quicksort).