Метка: основы алгоритмов

Сортировка пузырьком (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 элементов).

---

📢 Ваше мнение:

Пользуетесь ли вы сортировкой пузырьком в реальных проектах? Делитесь в комментариях!