Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що таке сортування вибором (selection sorts)?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

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

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

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

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

- Час: 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 (звичайна, нестійка версія)

```js
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, зсуваючи блок елементів на одну позицію вправо. Це зберігає відносний порядок рівних елементів ціною збільшення кількості присвоєнь.

```js
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 (рівно по одному на прохід за потреби).

### Варіації

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

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати691 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.