Что такое пузырьковая сортировка

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

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

Ниже учебная реализация. Она специально простая, но в ней уже есть две важные детали. Внутренний цикл сокращается, а флаг swapped позволяет остановиться раньше.

function bubbleSort(input) {
  const arr = [...input];

  for (let end = arr.length - 1; end > 0; end -= 1) {
    let swapped = false;

    for (let i = 0; i < end; i += 1) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]];
        swapped = true;
      }
    }

    if (!swapped) {
      break;
    }
  }

  return arr;
}

bubbleSort([5, 1, 4, 2]); // [1, 2, 4, 5]

В примере создается копия input. Это не обязательно для самого алгоритма, но безопаснее для frontend-кода: вызывающий код не получит неожиданно измененный массив.

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

Оптимизация с флагом swapped меняет лучший случай. Если массив уже отсортирован, первый проход не сделает ни одной перестановки, и алгоритм завершится за O(n). Но если массив отсортирован в обратном порядке, флаг почти не поможет, и время останется квадратичным.

На интервью для Frontend Developer bubble sort обычно не проверяет, будете ли вы писать его в продакшене. Вопрос чаще про базовое понимание алгоритмов. Вам нужно показать циклы, сравнение, обмен, Big O, мутацию данных и аккуратность с edge cases.

Для реальных списков, таблиц и выдач в UI bubble sort почти всегда слабый выбор. Большой массив может надолго занять главный поток. Интерфейс начнет подвисать, а пользователь увидит плохой отклик. В таком случае лучше использовать готовую сортировку, серверную сортировку, пагинацию, web worker или виртуализацию, если задача действительно тяжелая.

Пузырьковая сортировка может быть стабильной. Для этого нужно менять элементы местами только тогда, когда порядок действительно нарушен. Например, при сортировке по возрастанию условие arr[i] > arr[i + 1] не трогает равные элементы.

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

Хороший ответ можно построить так:

Пузырьковая сортировка сравнивает соседние элементы и меняет их местами, пока массив не станет отсортированным. После каждого прохода один элемент оказывается на своем месте, поэтому диапазон можно сокращать. В среднем и худшем случае это O(n^2), поэтому для больших данных в UI я бы ее не использовал. Можно добавить флаг перестановок, чтобы завершаться раньше на отсортированном массиве. Еще важно помнить, что классическая реализация мутирует массив, поэтому в React лучше сортировать копию.

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