Сортировка пузырьком на JavaScript

Сортировка - это процесс упорядочивания последовательности объектов. Объектами могут быть любые сущности которые можно сравнить.

Представь интернет магазин. Ты вводишь запрос в строку поиска и получаешь список результатов. Чтобы найти самый дешевый товар, тебе нужно выполнить сортировку по возрастанию цены.

Если ты просматриваешь свои траты с кредитной карты и хочешь начать с самых крупных, тебе тоже нужна сортировка.

Под капотом многих компьютерных программ сортировка используется для того, чтобы увеличить эффективность других операций, например поиска.

Сортировка пузырьком

Одним из простейших алгоритмов сортировки считается сортировка пузырьком. В ней все объекты становятся похожими на пузырьки воздуха, которые всплывают вверх к поверхности воды.

Мы сравниваем попарно соседние элементы массива и меняем их местами, если текущий элемент больше следующего.

Когда дойдем до конца массива, то самый последний элемент будет гарантированно на своем месте. Самый большой пузырек всплыл на поверхность воды.

Мы повторим процедуру еще раз, но уже до предпоследнего элемента.

После второй итерации, на своих позициях будет уже 2 последних элемента. Будем повторять алгоритм до тех пор, пока у нас не останется только первый элемент.

const bubbleSort = (arr) => {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i; j++) {
      if (arr[j] > arr[j + 1]) {
        let tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    }
  }
  return arr;
}

Для проверки создадим тестовый массив. Выведем на его на экран в начальном состоянии, сделаем сортировку и потом сделаем еще один console.log.

const testData = [0, -1, 4, 5, 2, -3];

console.log(testData);  // [ 0, -1, 4, 5, 2, -3 ]
bubbleSort(testData);   // вызываем функцию сортировки
console.log(testData);  // [ -3, -1, 0, 2, 4, 5 ]