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

Алгоритм сортировки — это алгоритм для упорядочивания элементов. Поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

Сортировка простыми обменами, сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Сложность алгоритма: O(n²).

Алгоритм

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

Псевдокод

Вход: массив A, состоящий из элементов A[0], A[1], ..., A[n-1], который требуется отсортировать по возрастанию

  цикл для i = 0, 1, ..., n − 1:
    цикл для j = i + 1, ..., n − 2:
      если A[j] > A[j+1], то:
        обменять местами элементы A[j] и A[j+1]

Оптимизация

• Внутренний цикл можно выполнять для [math]j = 0, 1, ..., n - i - 1[/math], где [math]i[/math] — номер итерации внешнего цикла, так как на [math]i[/math]-й итерации последние [math]i[/math] элементов массива уже будут правильно упорядочены.
• Внешний цикл можно заменить на цикл вида: пока произведится хотя бы один обмен на очередной итерации внешнего цикла, продолжать выполнение.

И тогда псевдокод будет выглядеть так:

t := истина
цикл пока t:
  t := ложь
  цикл для j = 0, 1, ..., n − 2:
    если A[j] > A[j+1], то:
      обменять местами элементы A[j] и A[j+1]
      t := истина