Сортировка пузырьком (Bubble Sort) — один из самых простых алгоритмов сортировки, который отлично подходит для обучения основам алгоритмов. В этой статье мы разберём:
- Как работает сортировка пузырьком
- Реализацию на PHP 8+ и JavaScript (ES6+)
- Оптимизацию алгоритма
- Примеры с пошаговым выводом
📌 Как работает сортировка пузырьком?
Алгоритм последовательно сравнивает соседние элементы массива и меняет их местами, если они расположены в неправильном порядке. Этот процесс повторяется до тех пор, пока массив не будет полностью отсортирован.
Основные шаги:
- Проход по массиву от начала до конца.
- Сравнение текущего элемента (
arr[j]
) со следующим (arr[j+1]
).
- Если
arr[j] > arr[j+1]
, меняем их местами.
- Повторяем, пока весь массив не станет упорядоченным.
🔹 Временная сложность:
- Худший случай: O(n²) (если массив отсортирован в обратном порядке).
- Лучший случай: O(n) (если массив уже отсортирован и используется оптимизация).
💻 Реализация на PHP (версия 8.0+)
<?php
function bubbleSort(array $arr): array {
$n = count($arr);
for ($i = 0; $i < $n; $i++) {
$swapped = false; // Флаг для оптимизации
for ($j = 0; $j < $n - $i - 1; $j++) {
if ($arr[$j] > $arr[$j + 1]) {
// Обмен значений (деструктуризация в PHP 7.1+)
[$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
$swapped = true;
}
}
// Если обменов не было, массив уже отсортирован
if (!$swapped) break;
}
return $arr;
}
// Пример использования
$array = [64, 34, 25, 12, 22, 11, 90];
$sortedArray = bubbleSort($array);
echo "Отсортированный массив: " . implode(", ", $sortedArray);
?>
🔸 Пояснение:
- Используется деструктуризация (
[$a, $b] = [$b, $a]
), доступная с PHP 7.1+.
- Флаг
$swapped
позволяет досрочно завершить сортировку, если массив уже упорядочен.
Вывод:
Отсортированный массив: 11, 12, 22, 25, 34, 64, 90
🌐 Реализация на JavaScript (ES6+)
1. Базовая версия
function bubbleSort(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
let swapped = false;
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Обмен значений (деструктуризация в ES6)
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
}
}
if (!swapped) break;
}
return arr;
}
const array = [64, 34, 25, 12, 22, 11, 90];
console.log("Отсортированный массив:", bubbleSort(array));
Вывод:
[11, 12, 22, 25, 34, 64, 90]
2. Версия с пошаговым выводом (для обучения)
function bubbleSortWithSteps(arr) {
const n = arr.length;
for (let i = 0; i < n; i++) {
let swapped = false;
console.log(`🔹 Проход ${i + 1}:`);
for (let j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
swapped = true;
console.log(` Поменяли ${arr[j]} ↔ ${arr[j + 1]}:`, [...arr]);
}
}
if (!swapped) break;
}
return arr;
}
const nums = [5, 3, 8, 4, 2];
console.log("Исходный массив:", nums);
bubbleSortWithSteps(nums);
console.log("Результат:", nums);
Вывод:
Исходный массив: [5, 3, 8, 4, 2]
🔹 Проход 1:
Поменяли 3 ↔ 5: [3, 5, 8, 4, 2]
Поменяли 4 ↔ 8: [3, 5, 4, 8, 2]
Поменяли 2 ↔ 8: [3, 5, 4, 2, 8]
🔹 Проход 2:
Поменяли 4 ↔ 5: [3, 4, 5, 2, 8]
Поменяли 2 ↔ 5: [3, 4, 2, 5, 8]
🔹 Проход 3:
Поменяли 2 ↔ 4: [3, 2, 4, 5, 8]
🔹 Проход 4:
Поменяли 2 ↔ 3: [2, 3, 4, 5, 8]
Результат: [2, 3, 4, 5, 8]
📌 Итог
- PHP 8+ и JavaScript (ES6+) поддерживают современный синтаксис (деструктуризацию).
- Оптимизация с флагом
swapped
ускоряет сортировку в лучшем случае до O(n).
- Сложность в худшем случае — O(n²), поэтому для больших массивов лучше использовать быструю сортировку
QuickSort
, сортировку слиянием MergeSort или встроенные методы (sort()
).
🚀 Где применять?
- Для обучения алгоритмам.
- Для небольших массивов (до 1000 элементов).
📢 Ваше мнение:
Пользуетесь ли вы сортировкой пузырьком в реальных проектах? Делитесь в комментариях!