Сортировка выбором

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

Зачем нужно

Selection Sort проста в реализации и делает минимальное число перестановок — O(n), в отличие от Bubble Sort. Это её единственное практическое преимущество: если запись (swap) дорога, а сравнение дёшево, Selection Sort предпочтительнее. В остальных случаях уступает Insertion Sort и тем более Quick/Merge Sort.

Где используется

  • Учебные цели: понимание базовых алгоритмов сортировки
  • Ситуации с дорогой записью и дешёвым сравнением (например, EEPROM)
  • Сортировка небольших массивов, где простота важнее скорости

Основной контент

Идея алгоритма

[5, 3, 8, 1, 2]

Шаг 1: min=1 (idx=3) → swap(0,3): [1, 3, 8, 5, 2]
Шаг 2: min=2 (idx=4) → swap(1,4): [1, 2, 8, 5, 3]
Шаг 3: min=3 (idx=4) → swap(2,4): [1, 2, 3, 5, 8]
Шаг 4: min=5 (idx=3) → swap(3,3): [1, 2, 3, 5, 8]

Реализация

function selectionSort(arr) {
  const a = [...arr];
  const n = a.length;

  for (let i = 0; i < n - 1; i++) {
    // Найти минимум в a[i..n-1]
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (a[j] < a[minIdx]) minIdx = j;
    }
    // Поставить минимум на позицию i
    if (minIdx !== i) {
      [a[i], a[minIdx]] = [a[minIdx], a[i]];
    }
  }
  return a;
}

console.log(selectionSort([5, 3, 8, 1, 2]));
// [1, 2, 3, 5, 8]

Сложность

Случай Время Память
Best case O(n^2) O(1)
Average case O(n^2) O(1)
Worst case O(n^2) O(1)

В отличие от Bubble Sort и Insertion Sort, не имеет лучшего случая — всегда n*(n-1)/2 сравнений.

Стабильность

Selection Sort нестабильна в стандартной реализации:

// Массив пар [значение, порядок]
const arr = [[3,'a'], [1,'b'], [3,'c'], [2,'d']];
// После Selection Sort порядок элементов с одинаковым значением 3 может измениться
// [1,'b'], [2,'d'], [3,'c'], [3,'a'] — 'a' и 'c' поменялись местами

Модификация с вставкой вместо swap делает её стабильной, но увеличивает сложность.

Сравнение квадратичных сортировок

Критерий Bubble Sort Selection Sort Insertion Sort
Время best O(n) O(n^2) O(n)
Число swap O(n^2) O(n) O(n^2)
Стабильная Да Нет Да
Онлайн Нет Нет Да

Частые ошибки

  • Предполагать, что Selection Sort быстрее других O(n^2) — на практике она часто медленнее Insertion Sort из-за отсутствия early termination.
  • Думать, что Selection Sort стабильна — стандартная реализация со swap нестабильна.
  • Применять для сортировки связного списка — нет произвольного доступа; Merge Sort лучше.

Связанные темы

Ресурсы