Алгоритм сортировки выборкой (Selection Sort): принцип работы

Также упоминается как: Линейный выбор с обменом, Сортировка выбором

Этот алгоритм тоже предельно прост: мы ищем самый маленький элемент в массиве и меняем его местами с первым. Затем ищем самый маленький из оставшихся и ставим на второе место, и так далее.

Идея метода сортировки

• Проходим весь неотсортированный "хвост" и находим в нем минимальный элемент.
• Меняем найденный минимум местами с первым элементом неотсортированной части - он занимает свое окончательное место.
• Граница сдвигается на 1 вправо; повторяем, пока не отсортируем весь массив.

Интерактивная схема ниже покажет, как сортировка выборкой раз за разом ищет минимум и ставит его на свое место.

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

Реализация на языке C

void SelectionSort(int arr[], int n) {
    int i, j, min_idx;

    // Двигаем границу неотсортированной части
    for (i = 0; i < n - 1; i++) {
        min_idx = i; // Предполагаем, что первый элемент - минимальный

        // Ищем реальный минимум в оставшейся правой части
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        // Делаем ОДИН обмен - ставим найденный минимум на место i
        if (min_idx != i) {
            Swap(&arr[min_idx], &arr[i]);
        }
    }
}