Сортировки: пузырёк и выбором наглядно

Урок объясняет, как упорядочить массив по возрастанию двумя классическими способами — пузырьковой сортировкой и сортировкой выбором.

Сортировка — это расстановка элементов массива по порядку (например, по возрастанию); один из важнейших алгоритмов в программировании.

Зачем сортировать

Отсортированные данные — повсюду: список контактов по алфавиту, товары по цене, результаты по рейтингу. В отсортированном массиве легко найти минимум (он первый), максимум (последний), медиану, быстро искать элемент. Сортировка — это базовый навык, который проверяют на экзаменах и собеседованиях. Мы разберём два самых наглядных алгоритма. Они не самые быстрые, но идеально подходят для понимания того, как вообще можно упорядочить данные.

Во всех примерах сортируем массив 5, 2, 8, 1, 4 по возрастанию.

Пузырьковая сортировка: идея

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

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

a = [5, 2, 8, 1, 4]
n = len(a)
for i in range(n - 1):           # проходы
    for j in range(n - 1 - i):   # сравниваем соседей
        if a[j] > a[j + 1]:      # левый больше правого?
            a[j], a[j + 1] = a[j + 1], a[j]  # меняем местами
print('Отсортировано:', a)

Вывод:

Отсортировано: [1, 2, 4, 5, 8]

Обратите внимание на n - 1 - i во внутреннем цикле: с каждым проходом «хвост» массива уже отсортирован, поэтому область сравнения сокращается. На Паскале обмен делается через временную переменную, как мы учили: temp := a[j]; a[j] := a[j+1]; a[j+1] := temp; (в Python это можно записать короче одной строкой, что вы и видите выше).

Пузырёк по шагам

Посмотрим, как меняется массив 5, 2, 8, 1, 4 после каждого полного прохода — это помогает прочувствовать алгоритм:

Сортировка выбором: идея

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

a = [5, 2, 8, 1, 4]
n = len(a)
for i in range(n - 1):
    min_pos = i                      # считаем текущий минимальным
    for j in range(i + 1, n):        # ищем минимум среди оставшихся
        if a[j] < a[min_pos]:
            min_pos = j
    a[i], a[min_pos] = a[min_pos], a[i]  # ставим минимум на место i
print('Отсортировано:', a)

Вывод:

Отсортировано: [1, 2, 4, 5, 8]

Внутренний цикл здесь — это знакомый нам поиск минимума, только в части массива. Найдя позицию минимума min_pos, мы один раз меняем элементы местами. Сортировка выбором делает меньше обменов, чем пузырёк, что иногда бывает плюсом.

Сравнение двух алгоритмов

Оба алгоритма медленные для больших массивов (для миллиона чисел используют быструю сортировку или встроенные средства). Но для школьных задач на сотню элементов они отлично подходят, а главное — учат думать. На больших данных в PascalABC.NET есть готовый метод a.Sort, но понимать «ручные» алгоритмы всё равно необходимо.

Попробуй сам

Отсортируйте массив 9, 3, 7, 1, 6 по убыванию (от большего к меньшему) пузырьком. Подсказка: достаточно поменять знак сравнения с > на <. Проверьте на Python:

a = [9, 3, 7, 1, 6]
n = len(a)
for i in range(n - 1):
    for j in range(n - 1 - i):
        if a[j] < a[j + 1]:        # знак изменён для убывания
            a[j], a[j + 1] = a[j + 1], a[j]
print('По убыванию:', a)

Вывод:

По убыванию: [9, 7, 6, 3, 1]

Частые ошибки

• Выход за границы в пузырьке. Сравнивая a[j] и a[j+1], внутренний цикл должен идти так, чтобы j+1 не вышел за массив. Отсюда верхняя граница n-1-i.
• Обмен без временной переменной (в Паскале). Прямой обмен теряет значение; нужен помощник temp.
• В сортировке выбором ищут значение вместо позиции. Запоминать нужно индекс минимума (min_pos), чтобы потом обменять элементы местами.
• Неверный знак сравнения. > даёт сортировку по возрастанию, < — по убыванию. Перепутали знак — получили обратный порядок.

Итоги

• Пузырьковая сортировка многократно сравнивает соседние элементы и меняет их местами; за проход наибольший «всплывает» в конец.
• Сортировка выбором на каждом шаге находит минимум оставшейся части и ставит его на очередное место.
• Оба алгоритма используют вложенные циклы и обмен элементов через временную переменную.
• Знак сравнения задаёт направление: > — по возрастанию, < — по убыванию.
• Эти сортировки медленные, но наглядные; для больших данных есть встроенный Sort.