Простые сортировки

Суть: вложенные циклы = O(n²)

Все простые сортировки используют вложенную структуру: внешний цикл проходов и внутренний для поиска/постановки одного элемента. n проходов × n сравнений за проход = O(n²).

Сортировка выбором: повторно ищи минимум

Сортировка выбором делит массив на две части: отсортированный префикс (слева) и неотсортированный суффикс (справа). На каждом проходе ищешь минимум в суффиксе и переносишь его в конец префикса.

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let minIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < arr[minIndex]) minIndex = j;
    }
    [arr[i], arr[minIndex]] = [arr[minIndex], arr[i]];
  }
}

Почему O(n²)? На проходе i ты сканируешь n - i элементов ища минимум. Всего: n + (n-1) + (n-2) + … + 1 = n(n+1)/2 = O(n²), без разницы на порядок входа.

Сортировка вставкой: растёшь отсортированный префикс

Сортировка вставкой строит отсортированный массив слева направо, по одному элементу. Для каждого нового элемента сканируешь префикс справа налево, сдвигаешь большие элементы вправо и вставляешь новый в правильное место.

function insertionSort(arr) {
  for (let i = 1; i < arr.length; i++) {
    const key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
}

Почему O(n²) в худшем случае? Когда массив развёрнут (худший случай), каждая вставка требует сдвига всех предыдущих элементов. Но вот магия: вставка адаптивна (adaptive — алгоритм меняет количество работы в зависимости от порядка ввода). Если массив уже отсортирован или почти отсортирован, цикл while не запускается (или один раз), так что алгоритм за O(n).

Сортировка пузырьком: повторно меняешь соседей

Сортировка пузырьком повторно ходит по массиву и меняет соседние элементы если они не в порядке. Большие элементы “всплывают” в конец. После каждого прохода самый правый неотсортированный на месте.

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

Тоже O(n²) в худшем. Проход за проходом, каждый сравнивает соседей. Пузырьёк медленнее всех трёх на практике — больше сравнений и обменов чем вставка.

Почему все O(n²) и на месте

Все три O(1) памяти — только переменные-индексы, временная для обмена. Все O(n²) в худшем из-за вложенного цикла. Но вставка особая: адаптивна. Когда встретишь код, что гоняет одну из трёх на маленьких подмассивах внутри самописного quicksort — скорее всего правильный выбор именно вставка, не выбор и не пузырёк.