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

Алгоритм:

N-1 раз выполняется следующая процедура:

    Для всех i  от 1 до N-1 c шагом 1:

если a_xi > a_x(i+1)   то поменять местами a_xi и a_x(i+1)

Легко видеть, что алгоритм требует порядка O(N²) арифметических операций.

Теорема. Алгоритм сортировки пузырьком является оптимальным по порядку времени выполнения среди алгоритмов, основанных на операции сравнения, если обмен местами двух элементов последовательности требует O(N) времени.

Ситуация, отраженная в теореме, возможна, например, при сортировке данных записанных на ленте, в какой-то мере, для данных, записанных на жестком диске. В быту данная ситуация реализуется в случае, когда у нас есть большой набор карточек с какими-то записями, выложенными в длинный ряд.

Доказательство. Рассмотрим следующую последовательность:

N, N-1, N-2, … 2, 1

Для любой сортировки этой последовательности следует первый в ней элемент поставить на последнее место (=порядка O(N-1) операций), второй элемент поставить на предпоследнее место (=порядка O(N-2) операций) и т.д. Итого, только перестановки займут не менее O(N²) времени, откуда мы получаем нижнюю оценку времени выполнения алгоритмов данного класса. Данная оценка достигается на предложенном алгоритме.