Двоичный (бинарный) поиск

Сортировка пузырьком

Сложность алгоритма определяется числом проверок условия a[j] > a[j+1] в цикле и числом обменов a[j] ↔ a[j+1], которое равно числу инверсий в исходной перестановке элементов a[1], a[2], …, a[n]. Определим число сравнений. В худшем случае верхняя граница b — 1 вложенного цикла for на каждом шаге внешнего цикла while будет уменьшаться на 1. тогда число сравнений равно

Основным достоинством алгоритма полной пузырьковой сортировки является легкость программирования. Сложность же алгоритма остается постоянной, не зависит от расположения исходных данных.

Сложность O( ), число операций

Двоичный (бинарный) поиск

Сложность O(n) = n

Сортировка слиянием (Merge sort)

Сложность алгоритма: O(n log n); выстраиваем первую и вторую половину списка отдельно, а затем — сливаем упорядоченные списки