Предварительные требования:

Некоторые базовые знания программирования на любом основном языке программирования, таком как Python, C++, Java и т. д. Знание асимптотических обозначений (см. эту статью) и способов их расчета (см. эту статью) для алгоритмов.

Предисловие:

Эта статья является первой частью серии «Алгоритмы». Алгоритмы сортировки — это класс алгоритмов, которые упорядочивают заданные входные данные в любом определенном порядке. Это помогает снизить время вычислений, необходимое для использования данных, поскольку данные расположены в определенном порядке. Сегодня мы поговорим о простом (но неэффективном) алгоритме сортировки Bubble Sort.

Объяснение:

Пузырьковая сортировка — очень популярный и простой алгоритм сортировки. Однако из-за своей простоты он также очень неэффективен. Тем не менее, это отличный способ начать свое путешествие в мир алгоритмов.

Если мы хотим отсортировать входные данные, скажем, в порядке возрастания, тогда он просто выбирает элемент и перемещает его вправо от списка входных данных до тех пор, пока следующий элемент справа не станет больше.

Отсюда и название пузырьковой сортировки, поскольку самый большой элемент «пузырится» до конца, точно так же, как самый большой пузырь из множества пузырьков поднимается наверх, а самый маленький оказывается внизу.

Поэтапную процедуру можно описать следующим образом:

  1. Выберите элемент.
  2. Сравните элемент с элементом справа.
  3. Если наш элемент больше, переместите его вправо и вернитесь к шагу 2. В противном случае ничего не делайте и вернитесь к шагу 2.
  4. Повторите для всех элементов.

Код:

Мы можем использовать эту пошаговую процедуру и написать код так:

BUBBLE_SORT(A):
  for i=0 upto A.size:
    for j=i upto A.size - 1:
      if A[j] > A[j+1]:
        swap A[j], A[j+1]

Вот объяснение кода:

for i=0 upto A.size:

Переменная «i» перемещается от 0 до A.size. Мы используем ее, чтобы наш алгоритм выполнил операцию для всех элементов (шаг 4).

for j=0 upto A.size - 1:

Переменная «j» изменяется от 0 до A.size — 1. Мы используем ее, чтобы выбрать элемент, который хотим сравнить (шаг 1).

if A[j] > A[j+1]:
  swap A[j], A[j+1]

Эта строка используется для сравнения элемента в позиции «j» с элементом в позиции «j+1», то есть следующим элементом (шаг 2). Если сравнение верно, то мы меняем местами два элемента, в противном случае мы просто выходим из цикла (шаг 3).

Производительность:

Теперь посчитаем временную сложность алгоритма.

Средний сценарий:

Первый цикл идет от i=0 до A.size, а второй цикл идет от j=0 до A.size-1. Поскольку оба цикла вложенные и зависят от размера массива A (назовем его N). Код будет иметь среднюю временную сложность ϴ(N²).

Наилучший сценарий:

Если массив A уже отсортирован, код будет выполняться как обычно, только оператор if внутри второго цикла не будет выполняться.

Следовательно, в лучшем случае временная сложность все равно будет равна Ω(N²).

Наихудший сценарий:

Если массив A полностью отсортирован, но совершенно противоположным образом, мы этого хотим. Тогда он также будет выполняться как обычно.

Следовательно, в наихудшем сценарии временная сложность все равно будет равна O(N²).