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

5.1 Определение сортировки пузырьком

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

Принцип работы:

1. Алгоритм проходит по списку и сравнивает каждую пару соседних элементов.
2. Если элементы находятся в неправильном порядке (первый больше второго для сортировки по возрастанию) — они меняются местами.
3. Этот процесс повторяется для всех пар элементов в списке.
4. После каждого полного прохода самый большой элемент «всплывает» на своё место (как пузырь на поверхности воды), и поэтому он больше не участвует в следующих проходах.
5. Процесс повторяется до тех пор, пока список не будет отсортирован.

Временная и пространственная сложность сортировки пузырьком

Временная сложность:

• В худшем случае: O(n^2) — происходит, когда элементы изначально упорядочены в обратном порядке.
• В среднем случае: O(n^2) — происходит для случайного расположения элементов.
• В лучшем случае: O(n) — происходит, когда элементы уже отсортированы (алгоритм может быть оптимизирован для этого случая, добавив проверку, произошёл ли обмен элементов за проход).

Пространственная сложность:

O(1) — так как алгоритм использует постоянное количество дополнительной памяти (только несколько переменных для хранения временных значений).

5.2 Реализация алгоритма

Алгоритм «сортировки пузырьком» — это самый простой и примитивный алгоритм сортировки списка/массива элементов. Он просто попарно сравнивает элементы и меняет их местами, если нужно.

Версия 1:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Обмен элементов

print("Отсортированный массив:", array)
# Вывод: Отсортированный массив: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Внутренний цикл (выделено зелёным) сравнивает элемент с его соседом справа. И если нужно — меняет элементы местами.

Версия 2:

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

После второй итерации справа будут уже 2 максимальных элемента, поэтому внутренний цикл можно вести не до n - 1, а до n - 1 - i. Где i — это количество пройденных итераций внешнего цикла.

Новый вариант будет выглядеть так:

array = [6, 43, 2, 1, 2, 1, 1, 1, 1, 6, 7, 8]
n = len(array)
            
for i in range(n):
    for j in range(n - 1 - i): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Обмен элементов

print("Отсортированный массив:", array)
# Вывод: Отсортированный массив: [1, 1, 1, 1, 1, 2, 2, 6, 6, 7, 8, 43]

Версия 3:

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

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

Реализация сортировки пузырьком на Python:

def bubble_sort(array):
    n = len(array)
    for i in range(n):
        swapped = False # Оптимизация: проверка, произошёл ли обмен
        for j in range(0, n - i - 1): if array[j] > array[j + 1]: array[j], array[j + 1] = array[j + 1], array[j]  # Обмен элементов
                swapped = True
        if not swapped:
            break  # Если обменов не было, массив уже отсортирован
    return array

# Пример использования:
array = [64, 34, 25, 12, 22, 11, 90]
sorted_array = bubble_sort(array)
print("Отсортированный массив:", sorted_array)
# Вывод: Отсортированный массив: [11, 12, 22, 25, 34, 64, 90]

2

Задача

Модуль 1: Python Core, 18 уровень, 4 лекция

Недоступна

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

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

Открыть

2

Задача

Модуль 1: Python Core, 18 уровень, 4 лекция

Недоступна

Урановые ломы в ртути

Урановые ломы в ртути

Открыть