Що таке сортування вибором (selection sorts)?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Сортування вибором - простий порівняльний алгоритм: на кожному кроці шукається мінімальний (або максимальний) елемент невідсортованої частини масиву й обмінюється з першим елементом цієї частини. Працює in-place, потребує O(1) додаткової пам'яті, має час O(n²) у найкращому/середньому/найгіршому випадках і зазвичай нестійка. Плюси: простота і мінімум обмінів; мінуси: повільна на великих даних.

Детальний розбір

Ідея алгоритму

Розбиваємо масив на дві частини: зліва - вже відсортована, справа - ще невідсортована.
Знаходимо індекс мінімального елемента у правій (невідсортованій) частині.
Міняємо цей мінімум місцями з першим елементом невідсортованої частини.
Зсуваємо межу відсортованої частини на один вправо і повторюємо процес до кінця.

Складність і властивості

Час: O(n²) у найгіршому, середньому і найкращому випадках (завжди робить ~n(n-1)/2 порівнянь).
Пам'ять: O(1) (in-place).
Кількість обмінів: O(n) (мінімальна серед простих квадратичних сортувань).
Стабільність: зазвичай нестійка (рівні елементи можуть поміняти місцями). Стабільна версія можлива при зсуві елементів замість обміну.
Адаптивність: не адаптивна - навіть для майже відсортованих масивів робить ті самі порівняння.

Псевдокод

text

for i = 0 to n-2:
  min = i
  for j = i+1 to n-1:
    if A[j] < A[min]:
      min = j
  swap A[i], A[min]

Приклад на JavaScript (звичайна, нестійка версія)

function selectionSort(arr, compare = (a, b) => a - b) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (compare(arr[j], arr[minIdx]) < 0) {
        minIdx = j;
      }
    }
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
  return arr;
}

// Приклад
// console.log(selectionSort([64, 25, 12, 22, 11])); // [11, 12, 22, 25, 64]

Покроковий приклад

Масив: [64, 25, 12, 22, 11]

text

Крок 1: мінімум 11 (індекс 4) → обмін з індексом 0
[11, 25, 12, 22, 64]
Крок 2: мінімум серед [25, 12, 22, 64] = 12 (індекс 2) → обмін з індексом 1
[11, 12, 25, 22, 64]
Крок 3: мінімум серед [25, 22, 64] = 22 (індекс 3) → обмін з індексом 2
[11, 12, 22, 25, 64]
Крок 4: мінімум серед [25, 64] = 25 → обмін не потрібен
[11, 12, 22, 25, 64]

Стабільна версія (зі зсувом замість обміну)

Щоб зробити сортування вибором стійким, знайдений мінімум не міняють місцями, а «вставляють» на позицію i, зсуваючи блок елементів на одну позицію вправо. Це зберігає відносний порядок рівних елементів ціною збільшення кількості присвоєнь.

function stableSelectionSort(arr, compare = (a, b) => a - b) {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (compare(arr[j], arr[minIdx]) < 0) {
        minIdx = j;
      }
    }
    const key = arr[minIdx];
    while (minIdx > i) {
      arr[minIdx] = arr[minIdx - 1];
      minIdx--;
    }
    arr[i] = key;
  }
  return arr;
}

// Приклад
// console.log(stableSelectionSort([3, 2, 2, 1])); // [1, 2, 2, 3] - вихідний порядок рівних «2» збережено

Коли доречно використовувати

Навчання і розбір базових принципів сортування.
Коли критична мінімальна кількість обмінів/записів (наприклад, носії з дорогою операцією запису).
Дуже малі масиви, де простота важливіша за швидкість (хоча на майже відсортованих даних сортування вставками зазвичай краще).

Часті питання на співбесіді

Чи стабільне сортування вибором? Зазвичай ні: обмін мінімуму з позицією i може поміняти порядок рівних елементів. Стабільність досягається зсувом замість обміну.
Чим відрізняється від бульбашкової сортування і сортування вставками? Бульбашкова робить багато обмінів, але може рано завершитися на майже відсортованих масивах; вибором - мало обмінів, але фіксована кількість порівнянь (не адаптивна). Вставками швидше на майже відсортованих даних, але робить більше переміщень; вибором економить обміни.
Скільки порівнянь/обмінів виконує? Порівнянь ≈ n(n-1)/2; обмінів не більше n-1 (рівно по одному на прохід за потреби).

Варіації

Вибір максимуму і розміщення його в кінець (еквівалентна ідея, прохід справа).
Двостороння сортування вибором: за один прохід знаходимо мінімум і максимум і ставимо їх на місця (зменшує кількість проходів приблизно вдвічі, але складніша в реалізації).
Для зв'язних списків: зручно реалізувати стійко шляхом переміщення вузлів без обміну значень.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.