Сортировка вставками на C: понятная реализация и сравнение с пузырьковой сортировкой

Сортировка вставками строит отсортированный массив по одному элементу. Алгоритм берёт очередной элемент из неотсортированной части и вставляет его в правильную позицию уже отсортированного префикса. Это тот же принцип, по которому человек раскладывает карты в руке: берёт следующую карту и сдвигает её влево до нужного места.

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

Массив делится на две части:

• Отсортированный префикс — начинается с a[0] и растёт на каждом шаге.
  
• Неотсортированный хвост — всё, что правее текущей позиции.
  

На каждой итерации алгоритм:

1. Берёт элемент a[i] (называется ключ).
   
2. Сравнивает его с элементами отсортированного префикса справа налево.
   
3. Сдвигает вправо все элементы, которые больше ключа.
   
4. Вставляет ключ в освободившуюся позицию.
   

После k итераций первые k + 1 элементов гарантированно отсортированы.

Реализация на C​

#include <stdio.h>

void insertion_sort(int a[], int n)
{
    for (int i = 1; i < n; i++) {
        int key = a[i];
        int j = i - 1;

        /* Сдвигаем элементы, большие key, на одну позицию вправо */
        while (j >= 0 && a[j] > key) {
            a[j + 1] = a[j];
            j--;
        }

        /* Вставляем key в найденную позицию */
        a[j + 1] = key;
    }
}

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

int main(void)
{
    int arr[] = {3, 7, 4, 9, 5, 2, 6, 1};
    int n = sizeof(arr) / sizeof(arr[0]);

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

    insertion_sort(arr, n);

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

    return 0;
}

Вывод программы:

До сортировки:  3, 7, 4, 9, 5, 2, 6, 1
После сортировки: 1, 2, 3, 4, 5, 6, 7, 9

Пошаговый разбор на примере​

Исходный массив: {3, 7, 4, 9, 5, 2, 6, 1}.

Шаг	Ключ	Действие	Состояние массива
1	7	7 > 3, остаётся на месте	3, 7, 4, 9, 5, 2, 6, 1
2	4	4 < 7 → сдвиг; 4 > 3 → стоп	3, 4, 7, 9, 5, 2, 6, 1
3	9	9 > 7, остаётся на месте	3, 4, 7, 9, 5, 2, 6, 1
4	5	сдвиг 9, 7; 5 > 4 → стоп	3, 4, 5, 7, 9, 2, 6, 1
5	2	сдвиг 9, 7, 5, 4; 2 < 3 → стоп	2, 3, 4, 5, 7, 9, 6, 1
6	6	сдвиг 9, 7; 6 > 5 → стоп	2, 3, 4, 5, 6, 7, 9, 1
7	1	сдвиг всех семи элементов	1, 2, 3, 4, 5, 6, 7, 9

На шаге 5 ключ 2 меньше всех элементов префикса, поэтому внутренний цикл проходит весь префикс — это худший случай для данной итерации.

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

Случай	Время	Пояснение
Лучший (массив уже отсортирован)	O(n)	Внутренний цикл не выполняется ни разу: a[j] > key сразу ложно
Средний	O(n²)	В среднем сдвигается половина элементов префикса
Худший (массив отсортирован в обратном порядке)	O(n²)	Каждый ключ сдвигает весь префикс

Дополнительная память — O(1): алгоритм работает на месте, используя только переменные key и j.

Сортировка вставками стабильна: равные элементы не меняют относительный порядок, потому что условие a[j] > key строго больше, а не больше-или-равно.

Сравнение с пузырьковой сортировкой​

Пузырьковая сортировка Пузырьковая сортировка на C: первый алгоритм сортировки с разбором по шагам многократно проходит по массиву, сравнивая соседние пары и меняя их местами, если порядок нарушен. Сортировка вставками вместо этого берёт один элемент и «проталкивает» его в нужное место.

Критерий	Сортировка вставками	Пузырьковая сортировка
Худший случай	O(n²)	O(n²)
Лучший случай	O(n)	O(n) с флагом раннего выхода
Средний случай	O(n²)	O(n²)
Число обменов (записей)	До O(n²) сдвигов, но каждый сдвиг — одна запись	До O(n²) обменов, каждый обмен — три записи
Адаптивность	Высокая: на почти отсортированных данных работает быстро	Низкая без оптимизаций
Стабильность	Да	Да
Работа на месте	Да	Да

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

Когда сортировка вставками — правильный выбор​

• Малые массивы. Для подмассивов размером до 10–50 элементов сортировка вставками быстрее более сложных алгоритмов из-за минимальных накладных расходов. Хорошие реализации quicksort переключаются на неё для малых подзадач.
  
• Почти отсортированные данные. Если каждый элемент отстоит от своей позиции не более чем на k мест, время работы составляет O(kn).
  
• Потоковая обработка. Алгоритм онлайн: можно обрабатывать элементы по мере поступления, не дожидаясь полного набора данных.
  
• Связные списки. Вставка в известную позицию связного списка выполняется за O(1) без сдвигов.
  

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

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

Условие while (j >= 0 && a[j] > key) должно проверять j >= 0 первым. Если поменять операнды местами, при j == -1 произойдёт обращение к a[-1] — неопределённое поведение.

/* НЕПРАВИЛЬНО — возможен выход за границу */
while (a[j] > key && j >= 0) { ... }

/* ПРАВИЛЬНО — короткое замыкание защищает от a[-1] */
while (j >= 0 && a[j] > key) { ... }

В C оператор && вычисляет левый операнд первым и не вычисляет правый, если левый ложен. Это называется коротким замыканием (short-circuit evaluation).

Неверная инициализация индекса​

Внешний цикл начинается с i = 1, а не с i = 0. Элемент a[0] сам по себе образует отсортированный префикс из одного элемента — его не нужно никуда вставлять.

Пропуск финальной вставки​

После выхода из внутреннего цикла нужно выполнить a[j + 1] = key. Если забыть эту строку, ключ будет потерян, а в массиве останется дубликат.

Сортировка по убыванию и обобщение на другие типы​

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

while (j >= 0 && a[j] < key) {
    a[j + 1] = a[j];
    j--;
}

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

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

void insertion_sort_str(char *arr[], int n)
{
    for (int i = 1; i < n; i++) {
        char *key = arr[i];
        int j = i - 1;

        while (j >= 0 && strcmp(arr[j], key) > 0) {
            arr[j + 1] = arr[j];
            j--;
        }

        arr[j + 1] = key;
    }
}

int main(void)
{
    char *words[] = {"delta", "alpha", "charlie", "bravo"};
    int n = sizeof(words) / sizeof(words[0]);

    insertion_sort_str(words, n);

    for (int i = 0; i < n; i++) {
        printf("%s\n", words[i]);
    }

    return 0;
}

Здесь сортируются указатели, а не сами строки, поэтому сдвиги дешёвые — перемещается только адрес.

Рекурсивный вариант​

Внешний цикл можно заменить рекурсией. Функция сортирует первые n - 1 элементов рекурсивно, затем вставляет a[n - 1] в отсортированный префикс:

void insertion_sort_recursive(int a[], int n)
{
    if (n <= 1)
        return;

    insertion_sort_recursive(a, n - 1);

    int key = a[n - 1];
    int j = n - 2;

    while (j >= 0 && a[j] > key) {
        a[j + 1] = a[j];
        j--;
    }

    a[j + 1] = key;
}

Рекурсивная версия не быстрее и расходует O(n) памяти на стек вызовов вместо O(1). Она приведена для понимания структуры алгоритма, а не для практического использования.

Как проверить корректность реализации​

Простой способ — сравнить результат с эталонной сортировкой из stdlib.h:

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

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

int main(void)
{
    int original[] = {5, 3, 8, 1, 9, 2, 7, 4, 6, 0};
    int n = sizeof(original) / sizeof(original[0]);

    int test[n], reference[n];
    memcpy(test, original, sizeof(original));
    memcpy(reference, original, sizeof(original));

    insertion_sort(test, n);
    qsort(reference, n, sizeof(int), cmp_int);

    if (memcmp(test, reference, sizeof(test)) == 0) {
        printf("OK\n");
    } else {
        printf("MISMATCH\n");
    }

    return 0;
}

Для более серьёзного тестирования стоит проверить граничные случаи: пустой массив (n == 0), один элемент, массив из одинаковых элементов, уже отсортированный и обратно отсортированный массивы.

Чек-лист перед использованием в реальном коде​

• Условие внутреннего цикла начинается с j >= 0.
  
• Внешний цикл стартует с i = 1.
  
• После внутреннего цикла выполняется a[j + 1] = key.
  
• Для массивов больше 50 элементов рассмотрите qsort или гибридный подход.
  
• Если данные почти отсортированы и приходят потоком — сортировка вставками остаётся одним из лучших вариантов.
  

Источники​

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