Даже если вы не программист, вы наверняка догадывались, что компьютеры умеют сортировать данные. Один из самых известных алгоритмов для этой цели — «пузырьковая сортировка» (Bubble Sort). Название звучит странно, но принцип работы довольно простой.
Как это работает
Представьте, что у нас есть ряд чисел, записанных в случайном порядке, например: 35, 13, 81, 24, 2. Задача: расположить их по возрастанию от меньшего к большему.
Чтобы решить задачу, мы шаг за шагом сравниваем соседние числа — проходим по списку через каждую пару чисел. Если первое число больше второго, мы меняем их местами. Если нет — идём дальше и повторяем процесс.
После первого прохода самое большое число «всплывает» в конец списка как пузырёк в воде — отсюда и название. Делаем несколько проходов, пока все числа не встанут на свои места.
Пример
Исходный список: [35, 13, 81, 24, 2]
Первый проход:
35 > 13 → меняем их местами: [13, 35, 81, 24, 2]
35 < 81 → оставляем: [13, 35, 81, 24, 2]
81 > 24 → меняем их местами: [13, 35, 24, 81, 2]
81 > 2 → меняем их местами: [13, 35, 24, 2, 81]
Теперь 81 на своём месте, а список имеет вид: [13, 35, 24, 2, 81]
Второй проход:
13 < 35 → оставляем: [13, 35, 24, 2, 81]
35 > 24 → меняем их местами: [13, 24, 35, 2, 81]
35 > 2 → меняем их местами: [13, 24, 2, 35, 81]
Теперь 35 на своём месте.
Третий проход:
13 < 24 → оставляем: [13, 24, 2, 35, 81]
24 > 2 → меняем их местами: [13, 2, 24, 35, 81]
Теперь 24 на своём месте.
Четвёртый проход:
13 > 2 → меняем их местами: [2, 13, 24, 35, 81]
При каждом проходе мы уменьшаем на 1 количество сравнений, потому что крайние числа справа уже стоят на своих местах. Итог: список отсортирован!
Аналог из реальной жизни:
Если представить, что люди выстраиваются по росту, пузырьковая сортировка работает так: каждый сравнивает себя с соседом и, если нужно, меняется местами. Процесс повторяется, пока все не встанут правильно.
Почему алгоритм пузырьковой сортировки популярен?
➕ Простота — его не сложно понять и написать даже новичку. По этой причине часто изучение алгоритмов начинают именно с него. Самое сложное здесь, пожалуй — понимать вложенные циклы.
➕ Наглядность — хорошо иллюстрирует базовые принципы сортировки. На этом алгоритме легко показать элементарные критерии сравнения (по возрастанию, убыванию, алфавиту и т.д.), а также проиллюстрировать время работы (которое далеко от совершенства).
Минусы алгоритма пузырьковой сортировки
➖ Медленный — для больших списков работает неэффективно. Когда мы имеем дело с простыми числами, это ещё не так страшно — компьютеры очень быстро умеют их считать. Однако часто в программировании приходится работать с крупными объектами, которые сами состоят из множества частей. В итоге из-за медленного алгоритма у вас просто всё зависнет.
➖ Много итераций — делает много лишних сравнений. Например, для 1000 элементов потребуется около 500 000 операций. Есть оптимизированные версии «пузырьковой сортировки» — они несколько улучшают ситуацию, но всё ещё не позволяют применять этот алгоритм на практике.
Где используется пузырьковая сортировка
🎓 В обучении программированию. Пузырьковая сортировка редко применяется в реальных проектах, но её часто изучают в учебных курсах, чтобы объяснить, как работают алгоритмы. И после этого уже легче перейти к изучению более сложных методов, которые пригодятся на практике.
Код алгоритма
Разберём код алгоритма. В интернете вам чаще всего будут предлагать примеры алгоритмов на языке Python. Что ж, исправим ситуацию 😎
Вот код алгоритма на JavaScript:
function BubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
sorted = true;
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
sorted = false;
}
}
if (sorted) break;
}
}
let arr = [2, 51, 18, 7, -12, 30, 5, 24, 84, 42];
console.log(arr); // [2, 51, 18, 7, -12, 30, 5, 24, 84, 42]
BubbleSort(arr);
console.log(arr); // [-12, 2, 5, 7, 18, 24, 30, 42, 51, 84]Здесь мы видим, что код заключён в функцию BubbleSort. Можно обойтись и без неё, но для удобства изучения и проверки работы алгоритмов их код чаще заключают в функции.
На входе у нас неотсортированный список из 10 случайных чисел: [2, 51, 18, 7, -12, 30, 5, 24, 84, 42]. После обработки функцией получаем отсортированный массив: [-12, 2, 5, 7, 18, 24, 30, 42, 51, 84].
Заглянем непосредственно внутрь нашей функции. Всё начинается с получения длины массива. Её чисто для удобства мы помещаем в переменную:
let len = arr.length;Теперь переходим к циклам. Здесь их два: внешний и вложенный. Чтобы легче понимать такие конструкции, удобно рассматривать их от внутреннего цикла к внешнему.
Сначала мы один раз проходим по всему списку, в результате чего самое большое число перемещается в конец (на самую правую позицию):
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
sorted = false;
}
}На первой итерации у нас i = 0 — это переменная из внешнего цикла, на неё пока не обращаем внимание, как и на переменную sorted (о ней — позже). Цикл у нас проходит от нулевого элемента до предпоследнего:
for (let j = 0; j < len - 1 - i; j++)Последний элемент нам в условии цикла не нужен, так как его в виде arr[j + 1] мы рассматриваем в теле цикла:
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
sorted = false;
}В записи выше проверяется условие и выполняется преобразование: если следующий элемент списка больше предыдущего, то они меняются местами.
Теперь, когда самое большое число переместилось в конец списка, нам снова нужно выполнить такую же операцию, но уже не включая это число (оно уже на своём месте). Для этого нам и нужен внешний цикл for (let i = 0; i < len — 1; i++):
for (let i = 0; i < len - 1; i++) {
sorted = true;
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
sorted = false;
}
}
if (sorted) break;
}В итоге внешним циклом мы 9 раз выполняем одно и то же действие: проверяем внутренним циклом пары чисел, каждый раз сокращая диапазон проверки на 1 (этот диапазон сокращается тоже благодаря условию внутреннего цикла).
Теперь перейдём к так называемому флагу sorted. Этот флаг позволяет нам не делать лишние итерации, если список уже отсортирован.
Представьте, что на входе у нас массив, где все числа расположены уже по порядку или, например, только два из них стоят не на своих местах — без флага sorted алгоритм всё равно 9 раз будет запускать внешний цикл, который, в свою очередь, запустит все итерации внутреннего.
В итоге нам потребуются все 45 итераций (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1), хотя мы могли бы обойтись всего, например, 17-ю для вот такого массива: [-12, 5, 2, 7, 18, 24, 30, 42, 51, 84] (здесь не по порядку стоят только числа 5 и 2) и 35-ю для массива из примера: [2, 51, 18, 7, -12, 30, 5, 24, 84, 42].
Рассмотрим чуть подробнее, как работает флаг sorted. Во внешнем цикле мы на каждой итерации придаём ему значение true, то есть сразу предполагаем, что в нашу функцию могут подать уже отсортированный массив:
for (let i = 0; i < len - 1; i++) {
sorted = true;
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
sorted = false;
}
}
if (sorted) break;
}Далее, если во внутреннем цикле у нас ни разу не выполнилось условие,
if (arr[j] > arr[j + 1])то флаг sorted не принимает значение false,
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
sorted = false;
}за счёт чего мы прерываем выполнение всего процесса далее в коде
if (sorted) break;и не делаем много лишней работы! 🙂
Отдельно бы хотелось ещё сказать об участке кода, где мы меняем местами числа, если выполняется условие if (arr[j] > arr[j + 1]):
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];Это такой быстрый способ в языке JavaScript поменять значения двух переменных без использования третьей. То есть применяется такая вот конструкция:
[a, b] = [b, a];Без неё нам пришлось бы использовать третью (лишнюю) переменную:
temp = a; // сохраняем значение a
a = b; // присваиваем a значение b
b = temp; // присваиваем b сохранённое значение aНа этом, пожалуй, всё! 🙂 Снова взглянем, что у нас получилось:
function BubbleSort(arr) {
let len = arr.length;
for (let i = 0; i < len - 1; i++) {
sorted = true;
for (let j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
sorted = false;
}
}
if (sorted) break;
}
}
let arr = [2, 51, 18, 7, -12, 30, 5, 24, 84, 42];
console.log(arr); // [2, 51, 18, 7, -12, 30, 5, 24, 84, 42]
BubbleSort(arr);
console.log(arr); // [-12, 2, 5, 7, 18, 24, 30, 42, 51, 84]Таков код алгоритма «пузырьковой сортировки» на JavaScript. Похожим образом этот алгоритм можно реализовать и на других языках программирования. Вот пара примеров:
Код на языке C++
#include <iostream>
bool sorted = false;
int arr[] = {2, 51, 18, 7, -12, 30, 5, 24, 84, 42};
int arr_length = sizeof(arr) / sizeof(arr[0]);
void printArray(int* begin, int* end)
{
for (int* p = begin; p < end; p++) std::cout << *p << " ";
std::cout << std::endl;
}
void bubbleSort(int array[], int arr_length)
{
for (int i = 0; i < arr_length - 1; i++)
{
sorted = true;
for (int j = 0; j < arr_length - 1 - i; j++)
{
if (arr[j] > arr[j + 1])
{
sorted = false;
int temp = arr[j + 1];
arr[j + 1] = arr[j];
arr[j] = temp;
}
}
if (sorted) break;
}
}
int main()
{
printArray(std::begin(arr), std::end(arr)); // 2, 51, 18, 7, -12, 30, 5, 24, 84, 42
bubbleSort(arr, arr_length);
printArray(std::begin(arr), std::end(arr)); // -12, 2, 5, 7, 18, 24, 30, 42, 51, 84
}Код на языке PHP
function bubbleSort($arr) {
for ($i = 0; $i < count($arr) - 1; $i++) {
$sorted = true;
for ($j = 0; $j < count($arr) - 1 - $i; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
$temp = $arr[$j];
$arr[$j] = $arr[$j + 1];
$arr[$j + 1] = $temp;
$sorted = false;
}
}
if ($sorted) break;
}
return $arr;
}
$arr = [2, 51, 18, 7, -12, 30, 5, 24, 84, 42];
print_r($arr); // 2, 51, 18, 7, -12, 30, 5, 24, 84, 42
echo '<br />';
$arr = bubbleSort($arr);
print_r($arr); // -12, 2, 5, 7, 18, 24, 30, 42, 51, 84Ну и куда же без всеми любимого Питона 😁👇
Код на языке Python
def print_arr(arr):
for i in arr:
print(i, end=' ')
print()
def bubble_sort(arr):
for i in range(len(arr) - 1):
is_sorted = True
for j in range(0, len(arr) - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
is_sorted = False
if is_sorted:
break
array = [2, 51, 18, 7, -12, 30, 5, 24, 84, 42]
print_arr(array) # 2 51 18 7 -12 30 5 24 84 42
bubble_sort(array)
print_arr(array) # -12 2 5 7 18 24 30 42 51 84Если вам ничего не понятно, но очень интересно, то рекомендую присмотреться к курсам по программированию от нашего партнёра, 👉 Михаила Русакова. У Михаила есть курсы как по упомянутым выше языкам программирования JavaScript, C++, PHP, Python, так и по многим другим языкам и направлениям.
Есть как платные, так и бесплатные версии — вы можете попробовать, и если вам не понравится тема или автор, то ничего не потеряете. Мы же со своей стороны очень рекомендуем попробовать, ведь учиться — никогда не рано и никогда не поздно! 🙂
Итог
«Пузырьковая сортировка» — отличный пример для изучения основ алгоритмов, но на практике её заменяют более быстрыми методами, такими как «сортировка слиянием» (Merge Sort) , «быстрая сортировка» (Quick Sort) или даже «сортировка вставками» (Insertion Sort) для небольших данных.
Этот алгоритм — как велосипед с тренировочными колёсами: помогает понять основы, но для серьёзных задач используют более сложные и быстрые методы.
Существуют улучшенные версии алгоритма — начиная от добавления специального флага, уменьшающего количество лишних итераций, заканчивая более самостоятельными и интересными модификациями. Например, есть «шейкерная сортировка» (Cocktail Shaker Sort), в которой проходы по списку делаются в обоих направлениях (сначала слева направо, потом справа налево), что немного ускоряет процесс.
Оставить комментарий к этой статье можно в нашем Telegram-канале:
Присоединяйтесь! 😉