re:re:actable
Урок 034 минуты чтения

Что такое bubble selection и insertion sort?

На этой странице
Кратко

Bubble, selection и insertion sort - простые сортировки с O(n^2). В production их почти не используют для больших данных, но они помогают понять сравнения, swaps, in-place сортировку и базовую сложность.

Вопрос

Как работают bubble, selection и insertion sort и когда простые сортировки полезны?

Bubble sort

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

Большие элементы "всплывают" вправо, как пузырьки. Первый проход по [5, 1, 4, 2]:

[5, 1, 4, 2]   5 > 1, меняем
[1, 5, 4, 2]   5 > 4, меняем
[1, 4, 5, 2]   5 > 2, меняем
[1, 4, 2, 5]   5 встал на свое место

После каждого прохода самый большой из оставшихся элементов оказывается в конце, поэтому внутренний цикл каждый раз на 1 короче (- i).

Если за проход не было ни одного обмена, массив уже отсортирован - можно выйти раньше. С таким флагом best case на отсортированном массиве становится O(n).

Selection sort

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

На каждом шаге ищем минимум в оставшейся части и ставим его на позицию i:

[5, 1, 4, 2]   минимум 1, меняем с позицией 0
[1, 5, 4, 2]   минимум из [5, 4, 2] - 2, меняем с позицией 1
[1, 2, 4, 5]   минимум из [4, 5] - 4, уже на месте

Selection sort всегда делает O(n^2) сравнений, даже на отсортированном массиве, зато не больше n обменов.

Insertion sort

function insertionSort(nums: number[]): number[] {
  for (let i = 1; i < nums.length; i++) {
    const current = nums[i]
    let j = i - 1
 
    while (j >= 0 && nums[j] > current) {
      nums[j + 1] = nums[j]
      j--
    }
 
    nums[j + 1] = current
  }
 
  return nums
}

Так сортируют карты в руке: берем следующую карту и вставляем в нужное место среди уже упорядоченных.

[5 | 1, 4, 2]   слева отсортированная часть [5]
[1, 5 | 4, 2]   1 вставили перед 5
[1, 4, 5 | 2]   4 вставили между 1 и 5
[1, 2, 4, 5]    2 вставили после 1

Хорош для маленьких или почти отсортированных массивов: если массив уже упорядочен, while ни разу не выполняется, и сложность O(n). Поэтому реальные движки используют insertion sort для маленьких кусков внутри более сложных сортировок.

Сравнение

АлгоритмBestWorstStableИдея
BubbleO(n) с флагомO(n^2)даменяем соседей
SelectionO(n^2)O(n^2)нетвыбираем минимум
InsertionO(n)O(n^2)давставляем в готовую часть

Что отвечать на собеседовании?

Это учебные O(n^2) сортировки. Bubble меняет соседние элементы, selection ищет минимум для текущей позиции, insertion вставляет текущий элемент в уже отсортированную левую часть. Insertion sort может быть эффективен на маленьких или почти отсортированных данных.

Что важно помнить: частые ошибки

  • Использовать bubble sort как реальное решение для больших данных.
  • Ошибаться в границах вложенного цикла.
  • Не понимать, какие алгоритмы in-place.
  • Забывать, что insertion sort имеет хороший best case на почти sorted data.
  • Не уметь объяснить идею без кода.

Мини-шпаргалка

  • Bubble - swap соседей.
  • Selection - ищет минимум.
  • Insertion - вставляет в sorted prefix.
  • Все обычно O(n^2).
  • In-place memory O(1).
  • Useful for learning, not large production data.

Документация

Wikipedia: Insertion sort, VisuAlgo: Sorting.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам