Сортування порівняннями

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Сортування непозначених гир за вагою, використовуючи лише терези, вимагає алгоритму сортування порівняннями

В алгоритмах сортування порівняннями для отримання інформації про розташування елементів вхідної послідовності використовуються тільки попарні порівняння елементів. Іншими словами, для визначення взаємного порядку двох елементів та виконується одна з перевірок або Ми не можемо використовувати значення самих елементів або отримувати інформацію про них іншим способом.

Приклади

[ред. | ред. код]

Модель дерева прийняття рішень

[ред. | ред. код]
Дерево прийняття рішень для сортування включенням на трьох елементах. Внутрішній вузол записаний як позначає порівняння між і Лист анотований перестановкою позначає впорядкування Виділеним позначені рішення для послідовності Перестановка означає, що відсортованим впорядкуванням є Всього існує можливих перестановок вхідних елементів і, отже, дерево прийняття рішень повинно мати не менше листів.

Ми можемо розглядати сортування порівняннями абстрактно, у термінах дерева прийняття рішень. Дерево прийняття рішень — повне двійкове дерево, яке представляє порівняння між елементами, які виконав певний алгоритм сортування порівняннями на наданих вхідних даних.

Нижня межа для найгіршої швидкодії

[ред. | ред. код]

Довжина найдовшого простого шляху від кореня до листа представляє кількість порівнянь які необхідно виконати в найгіршому випадку. З цього випливає, що кількість порівнянь в найгіршому випадку для певного алгоритму сортування порівняннями дорівнює висоті дерева прийняття рішень. Нижня межа для всіх дерев прийняття рішень в яких кожна перестановка є досяжним листом і є нижньою межею швидкодії для будь-якого алгоритму сортування порівняннями.

Теорема Будь-який алгоритм сортування порівняннями в найгіршому випадку вимагає порівнянь.

Доведення Зі сказаного вище, достатньо визначити висоту дерева прийняття рішень в якому кожна перестановка з'являється як досяжний лист. Розглянемо дерево висоти з досяжними листами, що відповідає сортуванню порівняннями для елементів. Через те, що кожна перестановок вхідних даних з'являється в якомусь листі, ми маємо оскільки повне двійкове дерево висоти має не більше ніж листів, маємо

що, якщо прологарифмувати, дає

(для доведення останнього рівняння зручно використати формулу Стірлінґа в логарифмічній формі).

Джерела

[ред. | ред. код]