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

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

Сортування непозначених гир за вагою, використовуючи лише терези, вимагає алгоритму сортування порівняннями

Приклади

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

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

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

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

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

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

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

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

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

Джерела

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.