Пузырьковая сортировка — это одна из первых сортировок, с которой я познакомился ещё в школе на уроках информатики. Писали мы тогда на Паскале: for i := 1 to n-1 do и if a[j] > a[j+1]. Простые циклы, обмен через временную переменную и долгожданный вывод отсортированного массива на экран.
С тех пор много чего изменилось, а пузырьковая сортировка так и осталась в учебном классе. В продакшен-коде она не встречается из-за своей квадратичной сложности O(n²).
В этой статье я решил вспомнить школьные годы и реализовать этот алгоритм на Go. Хоть он и не нужен для реальных задач, но он отлично иллюстрирует важные концепции: сравнение соседних элементов, проход по массиву с постепенным сокращением границы и ранний выход из цикла при оптимизации.
Давайте разберёмся, как это работает.
Эффективность и практическое применение
Прежде чем погрузиться в код, давайте оценим алгоритм с практической стороны.
Пузырьковая сортировка получила своё название из-за того, что большие элементы «всплывают» в конец массива, как пузырьки воздуха в воде. На каждом проходе самый большой элемент из неотсортированной части оказывается на своём месте в конце.
Временная сложность — O(n²) в худшем и среднем случае. Если массив уже отсортирован, оптимизированная версия отработает за O(n).
Пространственная сложность — О(1), так как сортировка происходит in-place, прямо в исходном слайсе, без выделения дополнительной памяти.
Когда использовать: практически никогда в продакшене. Алгоритм хорош как учебный пример для понимания работы вложенных циклов и обмена элементов. Его единственное практическое применение — когда нужно быстро объяснить принцип сортировки.
Реализация алгоритма на Go
Давайте рассмотрим чистую и понятную реализацию с подробными комментариями.
package main
import "fmt"
func bubbleSort(slice []int) []int {
n := len(slice)
// Внешний цикл - количество проходов
for i := 0; i < n-1; i++ {
// Внутренний цикл - проход по массиву и сравнение соседей
for j := 0; j < n-i-1; j++ {
if slice[j] > slice[j+1] {
// Меняем местами, если порядок нарушен
slice[j], slice[j+1] = slice[j+1], slice[j]
}
}
}
return slice
}
func main() {
someSlice := []int{64, 25, 12, 22, 11}
fmt.Println(bubbleSort(someSlice)) // [11 12 22 25 64]
}
Пошаговое объяснение логики
Внешний цикл (for i) — отвечает за количество проходов. После каждого полного прохода самый большой элемент «всплывает» в конец. Поэтому количество проходов n-1 — последний элемент автоматически окажется на месте.
Внутренний цикл (for j) — проходит по массиву и сравнивает соседние элементы. Граница внутреннего цикла уменьшается с каждым проходом (n-i-1), потому что последние i элементов уже отсортированы.
Сравнение (if slice[j] > slice[j+1]) означает: если левый элемент больше правого, то элементы нужно поменять местами — это соответствует сортировке данных по возрастанию. В случае сортировки по убыванию условие будет противоположным.
Обмен элементов в Go выполняется компактно — без использования временной переменной: slice[j], slice[j+1] = slice[j+1], slice[j].
Трассировка алгоритма пузырьковой сортировки
Давайте прогоним алгоритм для someSlice := []int{64, 25, 12, 22, 11} и посмотрим, как меняется состояние слайса на каждом проходе.
Исходное состояние: [64, 25, 12, 22, 11]
Проход 1 (i = 0)
Идём по массиву от индекса 0 до 3 (последний элемент не с чем сравнивать).
| Сравнение | Действие | Результат |
| 64 > 25? | Да → меняем | [25, 64, 12, 22, 11] |
| 64 > 12? | Да → меняем | [25, 12, 64, 22, 11] |
| 64 > 22? | Да → меняем | [25, 12, 22, 64, 11] |
| 64 > 11? | Да → меняем | [25, 12, 22, 11, 64] |
Результат прохода 1: [25, 12, 22, 11, 64]
64 «всплыл» в конец.
Проход 2 (i = 1)
Теперь последний элемент (64) не трогаем. Идём по индексам 0 до 2.
| Сравнение | Действие | Результат |
| 25 > 12? | Да → меняем | [12, 25, 22, 11, 64] |
| 25 > 22? | Да → меняем | [12, 22, 25, 11, 64] |
| 25 > 11? | Да → меняем | [12, 22, 11, 25, 64] |
Результат прохода 2: [12, 22, 11, 25, 64]
25 «всплыл» на предпоследнее место.
Проход 3 (i = 2)
Теперь последние два элемента (25, 64) не трогаем. Идём по индексам 0 до 1.
| Сравнение | Действие | Результат |
| 12 > 22? | Нет → ничего не делаем | [12, 22, 11, 25, 64] |
| 22 > 11? | Да → меняем | [12, 11, 22, 25, 64] |
Результат прохода 3: [12, 11, 22, 25, 64]
22 «всплыл» на свое место.
Проход 4 (i = 3)
Теперь последние три элемента (22, 25, 64) не трогаем. Идём по индексам 0 до 0.
| Сравнение | Действие | Результат |
| 12 > 11? | Да → меняем | [11, 12, 22, 25, 64] |
Результат прохода 4: [11, 12, 22, 25, 64]
Массив отсортирован.
Оптимизация: ранний выход
Классическая пузырьковая сортировка всегда делает n-1 проходов, даже если массив уже отсортирован. Добавим флаг swapped:
func bubbleSortOptimized(slice []int) []int {
n := len(slice)
for i := 0; i < n-1; i++ {
swapped := false
for j := 0; j < n-i-1; j++ {
if slice[j] > slice[j+1] {
slice[j], slice[j+1] = slice[j+1], slice[j]
swapped = true
}
}
// Если за весь проход не было обменов -
// массив отсортирован
if !swapped {
break
}
}
return slice
}
Как это работает: Если на очередном проходе не было ни одной замены, значит, массив уже отсортирован. Можно выходить из цикла досрочно.
Выигрыш: На уже отсортированном или почти отсортированном массиве алгоритм обрабатывает за O(n), а не за O(n²).
Важные нюансы реализации на Go
1. In-place сортировка
Функция модифицирует исходный слайс. Если нужно сохранить оригинал — сделайте копию:
func bubbleSortCopy(slice []int) []int {
sorted := make([]int, len(slice))
copy(sorted, slice)
// сортируем sorted...
return sorted
}
2. Компактный обмен
В Go можно менять значения местами без временной переменной:
// Классический способ temp := a a = b b = temp // Go-стиль a, b = b, a
3. Границы внутреннего цикла
Формула j < n-i-1 критически важна. Без -1 программа выйдет за границы слайса при обращении к j+1. А без n-i программа каждый раз будет проходить по всему слайсу, включая уже отсортированную часть.
4. Универсальность
Данная реализация работает только с []int. Для других типов нужно дублировать код или использовать дженерики (Go 1.18+).
Ключевой вывод
Пузырьковая сортировка — это классический учебный алгоритм, который показывает, как сравнивать и менять соседние элементы, выполнять многократные проходы по слайсу и оптимизировать код с помощью раннего выхода.
На практике она почти не применяется из-за квадратичной сложности, но понимание её принципов помогает при изучении более сложных алгоритмов, таких как быстрая сортировка или сортировка слиянием.
Главное, что нужно вынести: проход по слайсу с попарным сравнением соседей — фундаментальный паттерн, который всплывает в самых неожиданных местах за пределами сортировки.
А вы помните свой первый язык программирования, на котором писали пузырьковую сортировку? Делитесь в комментариях!
