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

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

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

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

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

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

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

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

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

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

• Сортування за лінійний час