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

Алгоритмы сортировки

Описание

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

Зачем это нужно

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

Визуализация

Начальное состояние: неотсортированный массив

Неотсортировано

Сравнение

Обмен

Отсортировано

Шаг 1 из 50

Скорость:

Сложность

Лучший случайO(n)

Средний случайO(n²)

Худший случайO(n²)

Сложность по памятиO(1)

Пример кода

function bubbleSort(arr: number[]): void {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let swapped = false;

    // Last i elements are already in place
    for (let j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        // Swap adjacent elements
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
        swapped = true;
      }
    }

    // If no swaps occurred, array is sorted
    if (!swapped) break;
  }
}

// Usage example
const unsorted = [64, 34, 25, 12, 22, 11, 90];
const sorted = [...unsorted]; // Copy to avoid mutating original
bubbleSort(sorted);
console.log(sorted); // [11, 12, 22, 25, 34, 64, 90]

Задачи на LeetCode

#26Remove Duplicates from Sorted Array

Лёгкая

#88Merge Sorted Array

Лёгкая