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

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

В алгоритмах сортування порівняннями для отримання інформації про розташування елементів вхідної послідовності $\langle a_{1},a_{2},\dots ,a_{n}\rangle$ використовуються тільки попарні порівняння елементів. Іншими словами, для визначення взаємного порядку двох елементів $a_{i}$ та $a_{j}$ виконується одна з перевірок $a_{i}<a_{j},a_{i}\leq a_{j},a_{i}=a_{j},a_{i}\geq a_{j}$ або $a_{i}>a_{j}.$ Ми не можемо використовувати значення самих елементів або отримувати інформацію про них іншим способом.

Приклади

• Сортування бульбашкою
• Пірамідальне сортування
• Сортування злиттям
• Сортування включенням
• Сортування вибором
• Швидке сортування
• Сортування змішуванням

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

Дерево прийняття рішень для сортування включенням на трьох елементах. Внутрішній вузол записаний як $i:j$ позначає порівняння між $a_{i}$ і $a_{j}.$ Лист анотований перестановкою $\langle \pi (1),\pi (2),\dots ,\pi (n)\rangle$ позначає впорядкування $a_{\pi (1)}\leq a_{\pi (2)}\leq \dots \leq a_{\pi (n)}.$ Виділеним позначені рішення для послідовності $\langle a_{1}=5,a_{2}=3,a_{3}=4\rangle .$ Перестановка $\langle 3,1,2\rangle$ означає, що відсортованим впорядкуванням є $a_{2}=3\leq a_{3}=4\leq a_{1}=5.$ Всього існує $3!=6$ можливих перестановок вхідних елементів і, отже, дерево прийняття рішень повинно мати не менше $6$ листів.

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

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

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

Теорема Будь-який алгоритм сортування порівняннями в найгіршому випадку вимагає $\Omega (n\lg {n})$ порівнянь.

Доведення Зі сказаного вище, достатньо визначити висоту дерева прийняття рішень в якому кожна перестановка з'являється як досяжний лист. Розглянемо дерево висоти $h$ з $l$ досяжними листами, що відповідає сортуванню порівняннями для $n$ елементів. Через те, що кожна $n!$ перестановок вхідних даних з'являється в якомусь листі, ми маємо $n!\leq l.$ оскільки повне двійкове дерево висоти $h$ має не більше ніж $2^{h}$ листів, маємо

$n!\leq l\leq 2^{h},$

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

$h\geq \lg {n!}=\Omega (n\lg {n})$ (для доведення останнього рівняння зручно використати формулу Стірлінґа в логарифмічній формі).

Джерела

• Дональд Кнут. Sorting and Searching // The Art of Computer Programming. — 3rd. — Massachusetts : Addison–Wesley, 1998. — Т. 3. — 780 с. — ISBN 0-201-89685-0.(англ.)
• Сортування за лінійний час