Что такое 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 для маленьких кусков внутри более сложных сортировок.
Сравнение
| Алгоритм | Best | Worst | Stable | Идея |
|---|---|---|---|---|
| Bubble | O(n) с флагом | O(n^2) | да | меняем соседей |
| Selection | O(n^2) | O(n^2) | нет | выбираем минимум |
| Insertion | O(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.