Топ питань
Часова шкала
Чат
Перспективи

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

З Вікіпедії, вільної енциклопедії

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

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

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

Приклади

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

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

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

Remove ads

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

Узагальнити
Перспектива

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

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

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

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

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

Джерела

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads