Как устроена сортировка пузырьком на примере списка оценок студентов

Механика работы алгоритма на оценках

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

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

На следующем проходе алгоритм снова стартует с начала массива. Теперь ему нет смысла проверять последнюю ячейку, ведь там уже зафиксирован абсолютный максимум. Число проверяемых пар на каждом витке сокращается ровно на единицу.

Реализация на языке Python

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

def bubble_sort(grades): n = len(grades) for i in range(n): swapped = False for j in range(0, n - i - 1): if grades[j] > grades[j + 1]: grades[j], grades[j + 1] = grades[j + 1], grades[j] swapped = True if not swapped: break return grades

Конструкция n - i - 1 во внутреннем цикле отсекает уже отсортированный хвост списка. Если список изначально был упорядоченным, флаг swapped останется со значением False после первой же итерации, и внешний цикл моментально прервёт работу.

Подсчёт операций для двадцати случайных чисел

Теоретическая сложность пузырьковой сортировки оценивается как O(n²). Это означает квадратичную зависимость количества шагов от размера входных данных. Для набора из 20 оценок точное число действий складывается из количества сравнений и количества перестановок в памяти.

Количество сравнений пар строго детерминировано и зависит исключительно от длины массива, если мы не используем досрочный выход. На первом проходе мы сравниваем 19 пар, на втором 18, на третьем 17, и так далее до 1 сравнения на последнем этапе. Сумма арифметической прогрессии от 1 до 19 вычисляется по формуле n * (n - 1) / 2. Подставив значение 20, получаем ровно 190 операций сравнения.

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

История появления и свойства алгоритма

Название bubble sort впервые появилось в печати в 1962 году благодаря американскому ученому Кеннету Айверсону, автору языка программирования APL. Сам принцип исследовался математиками и раньше, в середине 1950-х годов, как базовый способ упорядочивания перфокарт на электромеханических табуляторах.

Пузырьковый алгоритм обладает важным свойством стабильности. Если в списке студентов двое получили одинаковый балл, например 85, их взаимное расположение относительно друг друга после завершения работы программы останется неизменным. Условие grades[j] > grades[j + 1] строгое, поэтому равные элементы никогда не меняются местами.

Второе ключевое свойство заключается в сортировке на месте. Алгоритму требуется константный объём вспомогательной памяти O(1), ведь он модифицирует исходный массив, не создавая промежуточных копий данных в оперативной памяти компьютера.