Алгоритмы сортировки: метод пузырька

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

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

Пусть массив — 5 2 4 1. После 1-го прохода он станет 2 4 1 5, после 2-го — 2 1 4 5, после 3-го — 1 2 4 5. В Python соседние элементы сравнивают так: if a[j] > a[j + 1], а меняют местами так: a[j], a[j + 1] = a[j + 1], a[j]; эти действия повторяются во вложенных циклах for. Если за какой-то проход не было ни одного обмена, массив уже упорядочен, и работу можно прекратить.

Для сортировки n элементов нужно примерно n(n − 1)/2 сравнений, то есть время растёт пропорционально n². Для 1000 элементов это около 500 тысяч сравнений, а для 10 000 — около 50 миллионов. Поэтому сортировка пузырьком хороша для обучения, но неэффективна для больших данных. На практике используют готовые функции Python sorted() и list.sort(): они работают по гораздо более быстрому алгоритму (Timsort).

Главное

• Сортировка располагает элементы по возрастанию или убыванию.
• Сортировка пузырьком сравнивает соседние элементы и меняет местами те, что стоят неправильно.
• За каждый проход самый большой элемент встаёт на своё место — в конец.
• Проход без обменов означает, что массив упорядочен, и работу можно остановить.
• Нужно около n(n − 1)/2 сравнений, поэтому метод медленен на больших массивах.