Записки погромиста

Простое и Пошаговое Объяснение

Что такое Bubble Sort?

Bubble Sort (пузырьковая сортировка) — это один из самых простых алгоритмов сортировки, который помогает упорядочить элементы в массиве. Представьте, что у вас есть список чисел, которые нужно поставить в правильном порядке — от самого маленького до самого большого. Bubble Sort делает это, «пузыря» числа на правильные места, как будто бы они поднимаются вверх (всплывают), как пузырьки в воде.

Как работает Bubble Sort?

Bubble Sort работает, сравнивая два соседних числа и меняя их местами, если они стоят не в том порядке. Он повторяет этот процесс, пока весь массив не будет отсортирован.

Давайте разберём это на примере

Возьмем массив чисел: [5, 3, 8, 4, 2]. Наша цель — отсортировать этот массив по возрастанию, чтобы получить [2, 3, 4, 5, 8].

Шаг 1: Начнем с первого числа

1. Возьмем первое число (5) и сравним его со следующим (3).
2. Так как 5 больше 3, они не в правильном порядке. Меняем их местами.
3. Теперь наш массив выглядит так: [3, 5, 8, 4, 2].

Шаг 2: Переходим к следующей паре чисел

1. Сравним второе число (5) с третьим (8).
2. Они уже в правильном порядке (5 меньше 8), поэтому оставляем их как есть.
3. Массив остается [3, 5, 8, 4, 2].

Шаг 3: Сравниваем следующую пару

1. Теперь сравним 8 и 4.
2. 8 больше 4, значит, они не в правильном порядке. Меняем их местами.
3. Теперь наш массив выглядит так: [3, 5, 4, 8, 2].

Шаг 4: Сравниваем последнюю пару

1. Сравним 8 и 2.
2. Поскольку 8 больше 2, меняем их местами.
3. Теперь массив выглядит так: [3, 5, 4, 2, 8].

Теперь мы дошли до конца массива и самая большая цифра (8) оказалась на последнем месте. Но массив еще не полностью отсортирован, поэтому нам нужно повторить процесс.

Повторяем процесс

Мы повторяем шаги снова и снова, пока не отсортируем весь массив. На каждом «проходе» самые большие числа «всплывают» к концу массива, а меньшие числа постепенно остаются ближе к началу.

В нашем примере следующие проходы будут выглядеть так:

• Второй проход: [3, 4, 2, 5, 8]
• Третий проход: [3, 2, 4, 5, 8]
• Четвертый проход: [2, 3, 4, 5, 8]

Теперь массив отсортирован!

function bubbleSort(arr) {
  let swapped;
  do {
    swapped = false;
    for (let i = 0; i < arr.length - 1; i++) {
      if (arr[i] > arr[i + 1]) { // Если следующий элемент массива больше
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]; // Обмен
        swapped = true; // Помечаем, что был обмен
      }
    }
  } while (swapped); // Повторяем, пока были обмены
  return arr;
}

// Пример использования
let numbers = [5, 3, 8, 4, 2];
console.log(bubbleSort(numbers)); // Вывод: [2, 3, 4, 5, 8]