Сортування порівняннями
В алгоритмах сортування порівняннями для отримання інформації про розташування елементів вхідної послідовності використовуються тільки попарні порівняння елементів. Іншими словами, для визначення взаємного порядку двох елементів та виконується одна з перевірок або Ми не можемо використовувати значення самих елементів або отримувати інформацію про них іншим способом.
Приклади[ред. | ред. код]
- Сортування бульбашкою
- Пірамідальне сортування
- Сортування злиттям
- Сортування включенням
- Сортування вибором
- Швидке сортування
- Сортування змішуванням
Модель дерева прийняття рішень[ред. | ред. код]
Ми можемо розглядати сортування порівняннями абстрактно, у термінах дерева прийняття рішень. Дерево прийняття рішень — повне двійкове дерево, яке представляє порівняння між елементами, які виконав певний алгоритм сортування порівняннями на наданих вхідних даних.
Нижня межа для найгіршої швидкодії[ред. | ред. код]
Довжина найдовшого простого шляху від кореня до листа представляє кількість порівнянь які необхідно виконати в найгіршому випадку. З цього випливає, що кількість порівнянь в найгіршому випадку для певного алгоритму сортування порівняннями дорівнює висоті дерева прийняття рішень. Нижня межа для всіх дерев прийняття рішень в яких кожна перестановка є досяжним листом і є нижньою межею швидкодії для будь-якого алгоритму сортування порівняннями.
Теорема Будь-який алгоритм сортування порівняннями в найгіршому випадку вимагає порівнянь.
Доведення Зі сказаного вище, достатньо визначити висоту дерева прийняття рішень в якому кожна перестановка з'являється як досяжний лист. Розглянемо дерево висоти з досяжними листами, що відповідає сортуванню порівняннями для елементів. Через те, що кожна перестановок вхідних даних з'являється в якомусь листі, ми маємо оскільки повне двійкове дерево висоти має не більше ніж листів, маємо
що, якщо прологарифмувати, дає
- (для доведення останнього рівняння зручно використати формулу Стірлінґа в логарифмічній формі).
Джерела[ред. | ред. код]
|