Сортировка выбором на C: как искать минимум и постепенно упорядочивать массив

Принцип работы за одну минуту​

Сортировка выбором (selection sort) разбивает массив на две части: отсортированную слева и неотсортированную справа. На каждом шаге алгоритм находит минимальный элемент в неотсортированной части и меняет его местами с первым элементом этой части. Граница между частями сдвигается на одну позицию вправо. Процесс повторяется, пока не останется ни одного неотсортированного элемента.

Пример для массива {64, 25, 12, 22, 11}:

Исходный:    64  25  12  22  11
Шаг 1:       11  25  12  22  64   ← минимум 11 обменян с 64
Шаг 2:       11  12  25  22  64   ← минимум 12 обменян с 25
Шаг 3:       11  12  22  25  64   ← минимум 22 обменян с 25
Шаг 4:       11  12  22  25  64   ← 25 уже на месте, обмен не нужен

После четвёртого шага массив полностью упорядочен. Последний элемент всегда оказывается на своём месте автоматически, поэтому внешний цикл выполняется n - 1 раз.

Полная реализация на C​

#include <stdio.h>

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

void selection_sort(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        int min_idx = i;

        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        if (min_idx != i) {
            swap(&arr[i], &arr[min_idx]);
        }
    }
}

void print_array(const int arr[], int n)
{
    for (int i = 0; i < n; i++) {
        printf("%d", arr[i]);
        if (i < n - 1) printf(", ");
    }
    printf("\n");
}

int main(void)
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("До сортировки:  ");
    print_array(arr, n);

    selection_sort(arr, n);

    printf("После сортировки: ");
    print_array(arr, n);

    return 0;
}

Компиляция и запуск:

gcc -Wall -Wextra -o selection_sort selection_sort.c
./selection_sort

Ожидаемый вывод:

До сортировки:  64, 25, 12, 22, 11
После сортировки: 11, 12, 22, 25, 64

Пошаговый разбор логики​

Внешний цикл: граница отсортированной части​

Переменная i указывает на первую позицию неотсортированной части. После завершения итерации i элемент arr[i] уже стоит на своём окончательном месте. Цикл идёт от 0 до n - 2 включительно, потому что когда в неотсортированной части остаётся один элемент, он уже минимален среди оставшихся.

Внутренний цикл: поиск минимума​

Переменная min_idx хранит индекс наименьшего элемента, найденного на текущем проходе. Внутренний цикл начинается с i + 1 и проходит до конца массива. Если встречается элемент меньше текущего кандидата, min_idx обновляется.

Обмен​

После завершения внутреннего цикла минимальный элемент обменивается с arr[i]. Проверка if (min_idx != i) не обязательна для корректности, но экономит один вызов swap, когда элемент уже на месте.

Сложность алгоритма​

Параметр	Значение
Сравнения (всегда)	n(n − 1) / 2
Обмены (максимум)	n − 1
Время (худший случай)	O(n²)
Время (средний случай)	O(n²)
Время (лучший случай)	O(n²)
Дополнительная память	O(1)

Ключевая особенность: количество сравнений не зависит от начального порядка элементов. Даже полностью отсортированный массив потребует столько же сравнений, сколько и обратно отсортированный. Это отличает сортировку выбором от сортировки вставками, которая на почти упорядоченных данных работает значительно быстрее.

Количество обменов при этом ограничено n − 1 — не более одного на каждую итерацию внешнего цикла. Если записи в память дороги (например, при работе с EEPROM или flash), это преимущество становится существенным.

Типичные ошибки начинающих​

Выход за границы массива​

/* ОШИБКА: j начинается с 0 вместо i + 1 */
for (int j = 0; j < n; j++) {
    if (arr[j] < arr[min_idx]) {
        min_idx = j;
    }
}

Такой код не приведёт к аварийному завершению, но нарушит логику: элемент из уже отсортированной части может быть повторно выбран как минимум, и массив не будет отсортирован корректно.

Неправильная граница внешнего цикла​

/* ОШИБКА: i < n вместо i < n - 1 */
for (int i = 0; i < n; i++) {
    int min_idx = i;
    for (int j = i + 1; j < n; j++) { ... }
}

При i == n - 1 внутренний цикл не выполнится (условие j < n сразу ложно), поэтому формально ошибка не приводит к краху. Однако это лишний проход и признак непонимания алгоритма. В других вариациях подобная ошибка может вызвать обращение к arr[n].

Обмен без проверки на равенство индексов​

/* Работает корректно, но делает лишний обмен */
swap(&arr[i], &arr[min_idx]);

Если min_idx == i, обмен меняет элемент сам с собой. Результат не изменится, но при работе с крупными структурами (не int, а, например, массивы байтов) это лишнее копирование.

Потеря данных при обмене без временной переменной​

/* ОШИБКА: попытка обмена без temp */
*a = *a + *b;
*b = *a - *b;
*a = *a - *b;

Арифметический обмен переполняется при больших значениях int и не работает для типов с плавающей точкой. Всегда используйте временную переменную.

Сортировка по убыванию​

Достаточно изменить направление сравнения во внутреннем цикле:

void selection_sort_desc(int arr[], int n)
{
    for (int i = 0; i < n - 1; i++) {
        int max_idx = i;

        for (int j = i + 1; j < n; j++) {
            if (arr[j] > arr[max_idx]) {
                max_idx = j;
            }
        }

        if (max_idx != i) {
            swap(&arr[i], &arr[max_idx]);
        }
    }
}

Логика идентична, только ищем максимум и ставим его на текущую позицию.

Обобщённая версия через указатели на функции​

Для сортировки массивов произвольного типа можно передать функцию сравнения и размер элемента:

#include <stdio.h>
#include <string.h>

typedef int (*cmp_fn)(const void *, const void *);

void selection_sort_generic(void *base, size_t count, size_t size, cmp_fn cmp)
{
    char *arr = (char *)base;

    for (size_t i = 0; i + 1 < count; i++) {
        size_t min_idx = i;

        for (size_t j = i + 1; j < count; j++) {
            if (cmp(arr + j * size, arr + min_idx * size) < 0) {
                min_idx = j;
            }
        }

        if (min_idx != i) {
            char temp[size];
            memcpy(temp, arr + i * size, size);
            memcpy(arr + i * size, arr + min_idx * size, size);
            memcpy(arr + min_idx * size, temp, size);
        }
    }
}

int cmp_int(const void *a, const void *b)
{
    int va = *(const int *)a;
    int vb = *(const int *)b;
    return (va > vb) - (va < vb);
}

int main(void)
{
    int arr[] = {42, 7, 19, 3, 88};
    size_t n = sizeof(arr) / sizeof(arr[0]);

    selection_sort_generic(arr, n, sizeof(int), cmp_int);

    for (size_t i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Здесь char * используется как байтовый указатель для арифметики по элементам произвольного размера. Выражение (va > vb) - (va < vb) возвращает −1, 0 или 1 без риска переполнения, в отличие от va - vb.

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

Алгоритм	Сравнений (среднее)	Обменов	Поведение на отсортированных данных
Сортировка выбором	n(n−1)/2	≤ n−1	Не меняется
Сортировка вставками	~n(n−1)/4	до n(n−1)/2	O(n)
Пузырьковая сортировка	n(n−1)/2	до n(n−1)/2	O(n) с флагом

Сортировка выбором почти всегда быстрее пузырьковой и сортировки гномов по числу операций. Сортировка вставками в среднем делает вдвое меньше сравнений, но может выполнять значительно больше записей. Если записи дороги, а чтения дёшевы — выбор в пользу selection sort обоснован.

Для массивов размером менее 10–20 элементов сортировка выбором и вставками обычно быстрее рекурсивных алгоритмов вроде mergesort из-за меньших накладных расходов на рекурсию. Поэтому в гибридных реализациях (например, внутри introsort) для мелких подмассивов переключаются на вставки или выбор.

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

Классическая реализация с обменом нестабильна: обмен может переместить равные элементы в другом порядке. Если стабильность нужна, вместо обмена минимальный элемент вставляется в позицию i, а промежуточные элементы сдвигаются вправо. Это увеличивает число записей до O(n²), но сохраняет относительный порядок равных элементов. Для связных списков стабильный вариант реализуется естественно: минимум извлекается из неотсортированной части и добавляется в конец отсортированной.

Когда сортировка выбором уместна​

• Массив мал (менее 20 элементов) и нужен простой код без рекурсии.
  
• Записи в память значительно дороже чтений (flash, EEPROM).
  
• Требуется предсказуемое время выполнения вне зависимости от входных данных.
  
• Учебная задача для понимания базовых концепций сортировки.
  

Для больших массивов предпочтительны алгоритмы с O(n log n): heapsort, mergesort или qsort из стандартной библиотеки C.

Проверка результата​

Простая функция верификации, которую полезно добавлять в тесты:

#include <stdbool.h>

bool is_sorted(const int arr[], int n)
{
    for (int i = 1; i < n; i++) {
        if (arr[i] < arr[i - 1]) {
            return false;
        }
    }
    return true;
}

Вызывайте её после сортировки в отладочных сборках через assert(is_sorted(arr, n)). Это ловит ошибки в граничных условиях: пустой массив, один элемент, уже отсортированный массив, массив с дубликатами.

Граничные случаи​

Вход	Ожидаемое поведение
Пустой массив (n = 0)	Внешний цикл не выполняется, функция возвращает управление
Один элемент (n = 1)	Внешний цикл не выполняется
Все элементы равны	Обмены не происходят (при проверке min_idx != i)
Обратно отсортированный массив	Максимум обменов, но всё равно ≤ n − 1

Реализация выше корректно обрабатывает все перечисленные случаи без дополнительных проверок, потому что при n <= 1 условие i < n - 1 сразу ложно (при n = 0 переменная n - 1 равна -1, и цикл не стартует).

Источники​

• Selection sort - Wikipedia
  
• Main Page - Algorithms for Competitive Programming