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

Алгоритмы сортировкиЛёгкий

Описание

Сортировка выбором (Selection Sort) — это простой алгоритм сортировки, который многократно находит минимальный элемент из несортированной части и помещает его в начало. Он разделяет массив на отсортированную и несортированную части, постепенно расширяя отсортированную часть на один элемент за раз.

Зачем это нужно

Сортировка выбором — один из простейших алгоритмов сортировки для понимания и реализации. Хотя она не самая эффективная, она демонстрирует концепцию сортировки на месте и выбора. Она хорошо работает на небольших наборах данных и имеет преимущество в минимальном количестве перестановок — не более n-1.

Визуализация

Начальное состояние: неотсортированный массив

Неотсортировано

Минимум

Сравнение

Обмен

Отсортировано

Шаг 1 из 24

Скорость:

Как работает алгоритм

Сортировка выбором работает путём многократного нахождения минимального элемента из несортированной части и обмена его с первым несортированным элементом.

1. Поиск минимума

Просматриваем несортированную часть массива, чтобы найти наименьший элемент. Начинаем с первого несортированного элемента как текущего минимума.

2. Сравнение с оставшимися элементами

Сравниваем каждый оставшийся элемент с текущим минимумом. Если найден меньший элемент, обновляем индекс минимума.

3. Обмен с первым несортированным

После просмотра всей несортированной части, меняем местами минимальный элемент с первым несортированным:

Если минимум ещё не на своём месте, меняем его с первой несортированной позицией.
Отсортированная часть увеличивается на один элемент.

4. Повторяем, пока не отсортируем

Продолжаем находить минимум в оставшейся несортированной части и менять местами. Когда остаётся один несортированный элемент, массив полностью отсортирован.

Пример: сортировка массива [64, 25, 12, 22, 11]

Находим мин: 11 на позиции 4. Меняем с 64. Массив: [11, 25, 12, 22, 64].

Находим мин: 12 на позиции 2. Меняем с 25. Массив: [11, 12, 25, 22, 64]. Продолжаем: 22 меняется с 25. Результат: [11, 12, 22, 25, 64].

Сложность

Лучший случайO(n²)

Средний случайO(n²)

Худший случайO(n²)

Сложность по памятиO(1)

Анализ сложности

Временная сложность

O(n²) — даже в лучшем случае (уже отсортирован), сортировка выбором должна просмотреть всю несортированную часть для подтверждения минимума. Это даёт n(n-1)/2 сравнений.

O(n²) — в среднем каждый проход требует просмотра оставшихся несортированных элементов. Количество сравнений всегда n(n-1)/2 независимо от порядка входных данных.

O(n²) — худший случай совпадает с лучшим. Сортировка выбором всегда выполняет одинаковое количество сравнений, что делает её производительность предсказуемой.

Пространственная сложность

O(1) — сортировка выбором работает на месте, требуя лишь несколько переменных для отслеживания индекса минимума. Дополнительные массивы не нужны.

Нестабильная сортировка — равные элементы могут изменить относительный порядок при обмене. Например, если два равных элемента находятся на разных позициях, обмен может обратить их порядок.

Сравнение с другими сортировками

Сортировка выбором выполняет меньше перестановок, чем пузырьковая (не более n-1 против O(n²)), но всегда выполняет O(n²) сравнений. Сортировка вставками обычно быстрее на частично отсортированных данных. Преимущество сортировки выбором — предсказуемая производительность — она всегда занимает одинаковое время независимо от порядка входных данных.

Пример кода
function selectionSort(arr: number[]): void {
  const n = arr.length;

  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;

    // Find the minimum element in unsorted portion
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }

    // Swap minimum with current position
    if (minIdx !== i) {
      [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]];
    }
  }
}

// Usage example
const unsorted = [64, 25, 12, 22, 11];
const sorted = [...unsorted]; // Copy to avoid mutating original
selectionSort(sorted);
console.log(sorted); // [11, 12, 22, 25, 64]

Примеры использования в реальных задачах

Сортировка небольших наборов данных

Сортировка выбором подходит для небольших наборов данных (n < 20), где её простота перевешивает неэффективность. Она легко реализуется и отлаживается.

Среда с ограниченной памятью

Во встроенных системах или средах с ограниченной памятью, пространственная сложность O(1) делает сортировку выбором привлекательной, когда память важнее скорости.

Минимизация операций записи

Сортировка выбором выполняет не более n-1 перестановок, что меньше, чем у большинства других алгоритмов сортировки O(n²). Это полезно, когда операции записи дороги (например, flash-память, EEPROM).

Обучающий инструмент

Сортировка выбором часто является вторым изучаемым алгоритмом после пузырьковой сортировки. Она демонстрирует концепцию выбора и сортировки на месте, помогая студентам понять алгоритмическое мышление.

Поиск K наименьших элементов

Подход выбора можно адаптировать для нахождения k наименьших элементов без полной сортировки массива. Запустите k проходов сортировки выбором, чтобы получить k наименьших элементов по порядку.

Задачи на LeetCode

#88Merge Sorted Array

Лёгкая

#147Insertion Sort List

Средняя