Участник:Alexeyshekhanov/Сортировка пузырьком

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

Свойства и структура алгоритма

Общее описание алгоритма

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

Математическое описание алгоритма

Давайте представим список из n элементов, обозначим его как A[0], A[1], ..., A[n-1]. Сортировка пузырьком выполняет следующие шаги:

• Начнем с индекса i = 0.
• Для каждого i от 0 до n-1, сравниваем A[i] и A[i+1]. Если A[i] > A[i+1], меняем их местами.
• После первого прохода самый большой элемент окажется в конце списка.
• Уменьшаем n на 1 и повторяем шаги 1 и 2 для оставшихся элементов.
• Продолжаем выполнять проходы до тех пор, пока список не станет отсортированным.

Литература

• Левитин А. В. Глава 3. Метод грубой силы: Пузырьковая сортировка // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 144—146. — 576 с. — ISBN 978-5-8459-0987-9
• Абрамов С. А., Лекции о сложности алгоритмов. — М.: МЦНМО, 2009. - 256 с. - ISBN 978-5-94057-433-0