Пузырьковая сортировка (Bubble Sort)

Предположим, у нас есть массив из n целых чисел, который нужно отсортировать по возрастанию. Пузырьковая сортировка (Bubble Sort) — один из самых популярных и простых алгоритмов для достижения этой цели (но не забывайте, что он не очень быстрый — в большинстве производственных систем применяются другие методы для сортировки).

Принцип работы пузырьковой сортировки состоит в том, чтобы несколько раз пройтись по массиву и менять местами соседние элементы, если они неупорядочены. То есть, если , мы обмениваем эти два элемента, чтобы массив стал упорядочен по возрастанию.

Более конкретно, возьмём исходный массив a (предположим, это [4, 1, -1, 0, 2, 8]) и рассмотрим первые два элемента. Если они идут не по порядку, мы меняем их местами (в нашем случае получается [1, 4, -1, 0, 2, 8]). Затем переходим к следующей паре. Если и там порядок нарушен, снова меняем местами (в нашем случае [1, -1, 4, 0, 2, 8]). Мы повторяем эту процедуру, двигаясь к концу массива (в нашем примере это приведёт к [1, -1, 4, 0, 2, 8] → [1, -1, 0, 4, 2, 8] → [1, -1, 0, 2, 4, 8] → без изменений → готово).

Затем цикл начинается заново с начала массива. Мы снова сравниваем первую пару элементов и при необходимости меняем их местами, потом переходим к следующей паре и так далее. В нашем примере это даст: [1, -1, 0, 2, 4, 8] → [-1, 1, 0, 2, 4, 8] → [-1, 0, 1, 2, 4, 8] → без изменений.

Этот процесс повторяется до тех пор, пока весь массив не окажется полностью отсортированным:

a = [...]
while True:                                 # выполняем, пока массив не будет отсортирован
    is_sorted = True                        # если что-то меняем, устанавливаем значение в False
    for i in range(len(a) - 1):             # цикл от 0 до n-2
        if a[i] > a[i + 1]:                 # если элементы не по порядку
            is_sorted = False               # => массив не был отсортирован
            a[i], a[i + 1] = a[i + 1], a[i] # меняем a[i] и a[i + 1] местами
    
    if is_sorted:                           # если a уже отсортирован, выходим
        break
print(a)

Существует одна оптимизация, позволяющая избежать лишних действий:

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

a = [...]
for u in range(len(a) - 1, 0, -1):          # u = верхняя граница для внутреннего цикла
    is_sorted = True                        # если что-то меняем, устанавливаем значение в False
    for i in range(u):                      # проходим от 0 до u-1
        if a[i] > a[i + 1]:                 # если элементы не по порядку
            is_sorted = False               # => массив не отсортирован
            a[i], a[i + 1] = a[i + 1], a[i] # меняем a[i] и a[i + 1] местами
    
    if is_sorted:                           # выходим, если массив отсортирован
        break
print(a)

Худший случай для пузырьковой сортировки — это когда все числа упорядочены в обратном порядке (по убыванию). В таком варианте алгоритм выполнит порядка операций, что довольно много по сравнению с более быстрыми алгоритмами, о которых мы расскажем позже в курсе.

Давайте проследим, как алгоритм работает на нескольких массивах:

[4, 1, -1, 0, 2, 8]

u = 5

i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
i = 3 ⇒ swap ⇒ [1, -1, 0, 2, 4, 8]
i = 4 ⇒ do nothing

i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]

i = 0 ⇒ swap ⇒ [-1, 1, 0, 2, 4, 8]
i = 1 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
i = 2 ⇒ do nothing
i = 3 ⇒ do nothing

i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]

i = 0 ⇒ do nothing
i = 1 ⇒ do nothing
i = 2 ⇒ do nothing
is_sorted is True ⇒ break

i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]

[10, 5, 1, -1, -2, -7]

u = 5

i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]

i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]

i = 0 ⇒ swap ⇒ [1, 5, -1, -2, -7, 10]
i = 1 ⇒ swap ⇒ [1, -1, 5, -2, -7, 10]
i = 2 ⇒ swap ⇒ [1, -1, -2, 5, -7, 10]
i = 3 ⇒ swap ⇒ [1, -1, -2, -7, 5, 10]

i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]

i = 0 ⇒ swap ⇒ [-1, 1, -2, -7, 5, 10]
i = 1 ⇒ swap ⇒ [-1, -2, 1, -7, 5, 10]
i = 2 ⇒ swap ⇒ [-1, -2, -7, 1, 5, 10]

i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]

i = 0 ⇒ swap ⇒ [-2, -1, -7, 1, 5, 10]
i = 1 ⇒ swap ⇒ [-2, -7, -1, 1, 5, 10]

i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]

i = 0 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]

i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]

[1, 2, 3, 4, 5]

u = 5

i = 0 ⇒ do nothing
i = 1 ⇒ do nothing
i = 2 ⇒ do nothing
i = 3 ⇒ do nothing
i = 4 ⇒ do nothing
is_sorted is True ⇒ break

i = 0 ⇒ do nothing

Extracurricular (interesting video)

На YouTube есть замечательное видео от канала Lines That Connect, где более подробно разбирается алгоритм пузырьковой сортировки и объясняется интуиция, лежащая в основе кривой, которая возникает при работе алгоритма.

Задание

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

Вы решили написать программу, которая будет выводить индексы участников, которым нужно поменяться местами. Индексация начинается с 0.

Входные данные

Первая строка содержит одно целое число n (1 ≤ n ≤ 1000).

Следующая строка содержит n целых чисел (), обозначающих рост участников.

Выходные данные

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

Примеры

Input	Output
5 1 4 8 2 -1	2 3 3 4 1 2 2 3 1 2 0 1

Пояснение

2 ↔ 3 ⇒ 1 4 2 8 -1

3 ↔ 4 ⇒ 1 4 2 -1 8

1 ↔ 2 ⇒ 1 2 4 -1 8

2 ↔ 3 ⇒ 1 2 -1 4 8

1 ↔ 2 ⇒ 1 -1 2 4 8

0 ↔ 1 ⇒ -1 1 2 4 8

Задание

Входные данные

Выходные данные

Примеры

Пояснение

Constraints

To check your solution you need to sign in

Sign in to continue