Сортировка пузырьком (bubble sort) в Python
В этом уроке вы реализуете сортировку пузырьком и добавите досрочную остановку, как только список окажется отсортированным.
Введение
Какую задачу это решает
Сортировка повсюду, и понимание того, как она работает, помогает рассуждать о скорости. Пузырьковую сортировку легче всего проследить шаг за шагом, поэтому она обычно служит первым примером, хотя настоящие программы используют более быстрые.
Пример из жизни
Пузырьковая сортировка похожа на построение детей по росту, когда можно только менять местами двух соседей. Пройдите вдоль ряда и меняйте каждую пару, где впереди стоит более высокий ребёнок. После одного прохода самый высокий оказывается в конце, как пузырёк, поднявшийся на поверхность. Повторяйте, пока проход не обойдётся без обменов.
result[index] > result[index + 1]👫 Впереди стоит более высокий?result[index], result[index + 1] = ...🔄 Поменять двух соседей местамиfor end in range(len(result) - 1, 0, -1):🚶 Снова пройти ряд, каждый раз на одного корочеif not swapped: break✅ За весь проход ни одного обмена: ряд отсортированПузырьковая сортировка многократно проходит по списку, меняя местами соседние элементы, стоящие в неверном порядке, пока полный проход не обойдётся без обменов; в общем случае она занимает время O(n²).
Главное
result = values.copy()сортирует копию, поэтому список вызывающего не меняется.if result[index] > result[index + 1]:меняет местами пару в неверном порядке.endуменьшается после каждого прохода, потому что наибольшие значения уже в конце.if not swapped: breakостанавливается раньше, если проход обошёлся без обменов, поэтому отсортированный ввод заканчивается за один проход.
Когда это нужно?
- Изучение того, как работает сортировка сравнениями.
- Крошечные списки в учебных инструментах и визуализациях.
- Проверка за один проход, отсортирован ли список.
Когда это не нужно
- Любая настоящая программа:
sorted()иlist.sort()гораздо быстрее (O(n log n)) и проверены. - Списки больше нескольких сотен элементов: число сравнений растёт как квадрат длины.
Визуализация: Сортировка пузырьком (bubble sort) в Python
O(n²)Нажимайте Запуск или Шаг, чтобы следить за сравнениями и перемещением данных.
Пример кода
def bubble_sort(values):
result = values.copy()
for end in range(len(result) - 1, 0, -1):
swapped = False
for index in range(end):
if result[index] > result[index + 1]:
result[index], result[index + 1] = result[index + 1], result[index]
swapped = True
if not swapped:
break
return result
print(bubble_sort([5, 1, 4, 2, 8]))
Результат выполнения
[1, 2, 4, 5, 8]
Разбор кода
После каждого прохода самое большое значение неотсортированной части уже стоит на своём окончательном месте, поэтому следующий проход короче на один элемент. Переменная swapped показывает, был ли обмен за проход. Если обменов не было, список уже отсортирован и цикл останавливается раньше. В худшем случае сложность O(n²), поэтому для больших объёмов данных алгоритм не подходит.
Измените значения и запустите программу в онлайн-компиляторе Python CodeUtility без локальной установки Python.
Упражнения для практики
Попробуйте изменить код по подсказкам ниже. Если менять код и смотреть на результат, урок запомнится гораздо лучше, чем при простом чтении.
- Проверьте работу на пустом списке, списке из одного элемента и списке с повторами.
- Выводите состояние после каждого шага, чтобы увидеть алгоритм в действии.
- Измерьте время работы на 100, 1 000 и 10 000 элементах и сравните с другим решением.
Частые ошибки
Выход на один индекс дальше
result[index + 1] выходит за конец, когда index доходит до последней позиции.
for index in range(len(result)):
if result[index] > result[index + 1]:
for index in range(end):
if result[index] > result[index + 1]:
Закончили этот урок?
Отметьте его как изученный, чтобы следить за прогрессом.
Попрактикуйтесь на задаче
Примените материал этого урока к реальной задаче. Каждая задача запускается в браузере, с мгновенными тестами и разбором от ИИ.
- Count Inversions Count the out-of-order pairs in a list. Сложно
- Медиана списка Найдите среднее значение списка после сортировки. Легко