Сортировка вставками на СИ

Сортировка вставками – один из наиболее простых и эффективных алгоритмов сортировки. Он был изобретен в 1951 году английским математиком Эдмундом Халли во время его работы над компьютером EDSAC. Сортировка вставками работает по принципу "прогрессивного уточнения", то есть на каждом шаге из неотсортированной части массива берется один элемент и вставляется на нужное место в уже отсортированную часть.

Описание алгоритма

Рассмотрим работу алгоритма на примере сортировки массива целых чисел. Пусть дан массив a размером n.

Взять первый элемент массива и считать его отсортированным подмассивом.
Для каждого следующего элемента массива выполнить следующие действия:
- Сравнить следующий элемент с элементами отсортированной части, начиная с последнего.
- Если элемент меньше, чем текущий элемент отсортированной части, то сдвинуть его на одну позицию вправо.
- Повторять предыдущий пункт, пока следующий элемент не станет больше или равен текущему элементу отсортированной части.
- Вставить следующий элемент на найденное место.
Повторять пункты 2 и 3 для всех оставшихся элементов массива.

Реализация на языке СИ

void insertion_sort(int *a, int n) {
    int i, j, temp;
    for(i = 1; i < n; i++) {
        temp = a[i];
        j = i - 1;
        while (temp < a[j] && j >= 0) {
            a[j+1] = a[j];
            j--;
        }
        a[j+1] = temp;
    }
}

В функции insertion_sort сначала объявляются переменные i, j и temp. Переменная i обозначает текущий элемент массива, который мы собираемся сравнить с элементами отсортированной части. Переменная j – это индекс последнего элемента отсортированной части, а temp – это значение текущего элемента, которое мы временно сохраняем.

Далее происходит сравнение элемента a[i] со всеми элементами отсортированной части (a[0]...a[j]). Если текущий элемент меньше какого-то элемента отсортированной части, то он сдвигается на одну позицию вправо, пока не найдется нужное место. Индекс j уменьшается на единицу, чтобы мы могли сравнивать с предыдущим элементом отсортированной части.

Когда мы находим место для текущего элемента, он вставляется в отсортированную часть массива на позицию j+1.

Пример использования

Приведем пример использования функции insertion_sort на языке СИ:

#include <stdio.h>

int main() {
    int a[] = {5, 4, 3, 2, 1};
    int n = sizeof(a) / sizeof(a[0]);
    insertion_sort(a, n);
    for(int i = 0; i < n; i++) {
        printf("%d ", a[i]);
    }
    return 0;
}

На выходе мы получим отсортированный массив {1, 2, 3, 4, 5}.

Вывод

Сортировка вставками – это простой и эффективный алгоритм сортировки, который может быть использован для сортировки массивов любого размера и типа. Реализовать его на языке СИ довольно просто, и он показывает быстрые результаты на практике.