Шаг 1

В этой демонстрации реализуем на практике сортировку пузырьком из предыдущей статьи. Будет лучше, если сначала вы попробуйте реализовать её самостоятельно!

/*
bubbleSort([5, 3, 2, 1]) => [1, 2, 3, 5]
bubbleSort([1, 2, 3]) => [1, 2, 3]
*/

function bubbleSort(array) {
  return [];
}

Шаг 2

Сначала напишем простую версию, без разделения на сортированный и несортированный подмассивы, а потом оптимизируем её. Для этого нам нужно проитерироваться по всему массиву n раз.

import {logIteration} from "./logger";

/*
bubbleSort([5, 3, 2, 1]) => [1, 2, 3, 5]
bubbleSort([1, 2, 3]) => [1, 2, 3]
*/

function bubbleSort(array) {
  // проходим весь массив столько раз, сколько в нём элементов - 1, потому что, как мы выяснили в статье,
  // последняя итерация "добьет" сразу два последних элемента
  for (let i = 0; i < array.length - 1; i++) {
    // в рамках каждого прохода нам тоже нужно просматривать на один элемент меньше,
    // ведь для последнего элемента мы не найдем следующий, с которым будем его сравнивать
    for (let j = 0; j < array.length - 1; j++) {
      // ...
    }

    logIteration(array);
  }

  return array;
}

bubbleSort([56, 87, 18, 92, 42, 31, 44, 82, 36, 91]);

Шаг 3

Осталось лишь дописать попарное сравнение элементов и их смену, и наша сортировка готова!

import {logIteration} from "./logger";

/*
bubbleSort([5, 3, 2, 1]) => [1, 2, 3, 5]
bubbleSort([1, 2, 3]) => [1, 2, 3]
*/

function bubbleSort(array) {
  // проходим весь массив столько раз, сколько в нём элементов - 1, потому что, как мы выяснили в статье,
  // последняя итерация "добьет" сразу два последних элемента
  for (let i = 0; i < array.length - 1; i++) {
    // в рамках каждого прохода нам тоже нужно просматривать на один элемент меньше,
    // ведь для последнего элемента мы не найдем следующий, с которым будем его сравнивать
    for (let j = 0; j < array.length - 1; j++) {
      // если элемент слева больше элемента справа...
      if (array[j] > array[j + 1]) {
        /// ... меняем их местами
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }

    logIteration(array);
  }

  return array;
}

bubbleSort([56, 87, 18, 92, 42, 31, 44, 82, 36, 91]);

Шаг 4

А теперь можем дописать небольшую оптимизацию. Мы точно знаем, что в каждый проход самое большое число «всплывает» в конец массива, поэтому и проходить по ним каждый раз не нужно. Каждый проход будем игнорировать уже отсортированную часть массива. Важно понимать, что хотя мы и отсекли часть ненужных проходов, общая сложность алгоритма всё ещё квадратичная! Можете убедиться в этом сами, например, посчитав количество операций для списка из трёх и четырёх элементов.

import {logIteration} from "./logger";

/*
bubbleSort([5, 3, 2, 1]) => [1, 2, 3, 5]
bubbleSort([1, 2, 3]) => [1, 2, 3]
*/

function bubbleSort(array) {
  // проходим весь массив столько раз, сколько в нём элементов - 1, потому что, как мы выяснили в статье,
  // последняя итерация "добьет" сразу два последних элемента
  for (let i = 0; i < array.length - 1; i++) {
    // в рамках каждого прохода нам тоже нужно просматривать на один элемент меньше,
    // ведь для последнего элемента мы не найдем следующий, с которым будем его сравнивать
    // а ещё каждую итерацию будем смотреть на один элемент поменьше, ведь справа будет уже сортированная его часть
    for (let j = 0; j < array.length - 1 - i; j++) {
      // если элемент слева больше элемента справа...
      if (array[j] > array[j + 1]) {
        /// ... меняем их местами
        [array[j], array[j + 1]] = [array[j + 1], array[j]];
      }
    }

    logIteration(array);
  }

  return array;
}

bubbleSort([56, 87, 18, 92, 42, 31, 44, 82, 36, 91]);

File logger

const results = document.getElementById('results')

export function logIteration(array) {
  const result = document.createElement('li');

  result.innerHTML = `[${array.join(', ')}]`;

  results.appendChild(result);
}