Алгоритмы JavaScript: Сортировка пузырьков

Пузырьковая сортировка – это простой алгоритм сортировки, но он также довольно неэффективен, так как его наихудший случай – O(n^2) сложность.

Но об этом стоит узнать.

Мы проходим по массиву и продолжаем сравнивать один элемент с другим рядом с ним.

Если предмет справа меньше, мы меняем местами две позиции.

Вот наша реализация:

const bubbleSort = (originalArray) => {
  let swapped = false

  const a = [...originalArray]

  for (let i = 1; i < a.length - 1; i++) {
    swapped = false

    for (let j = 0; j < a.length - i; j++) {
      if (a[j + 1] < a[j]) {
        ;[a[j], a[j + 1]] = [a[j + 1], a[j]]
        swapped = true
      }
    }

    if (!swapped) {
      return a
    }
  }

  return a
}

Вы можете видеть, что O(n^2) происходит из-за того, что мы зацикливаем массив 2 раза, чтобы проверить, нужно ли нам поменять элемент на тот, что справа.

Мы начинаем с первого элемента и сравниваем его со вторым. Если первый больше, мы меняем их местами. В противном случае мы оставляем все как есть и переключаемся на второй элемент массива. Мы сравниваем его с третьим. Опять же, если 2-й больше 3-го, мы меняем их местами и продолжаем менять местами, пока он не найдет свою позицию в массиве.

Вот пример:

Предположим, мы запустим bubbleSort([2, 1, 3]) .

Сначала мы сравниваем 2 с 1. 2 > 1, поэтому мы меняем их местами:

1 2 3

затем мы сравниваем 2 с 3. 2 < 3, поэтому оставляем все как есть. Мы пропускаем последний элемент, так как знаем, что из-за нашего рабочего процесса он всегда будет самым большим элементом.

Оригинал: “https://flaviocopes.com/bubble-sort-javascript/”