Сортировка вставками - C (СИ) (153324)

Формулировка задачи:

Сортировка вставками: пусть первые k элементов упорядочены по возростанию. Берется (k+1)-ый элемент и размещается среди первых k так, чтобы упорядоченными оказались k+1 элементов. Этот метод применяется при k от 1 до n-1

Решение задачи: «Сортировка вставками»

Листинг программы

void insertSort(int* a, int size) 
{
    int i, j, tmp;
    for (i = 1; i < size; ++i) // цикл проходов, i - номер прохода
    {
        tmp = a[i]; 
        for (j = i - 1; j >= 0 && a[j] > tmp; --j) // поиск места элемента в готовой последовательности 
            a[j + 1] = a[j];    // сдвигаем элемент направо, пока не дошли
        a[j + 1] = tmp; // место найдено, вставить элемент    
    }
}

Объяснение кода листинга программы

В функции insertSort определены три переменные: i, j, tmp. Значение i и j инициализируются на 1 и 0 соответственно, а tmp не инициализируется и будет использоваться как временная переменная.
Функция insertSort принимает два аргумента: массив a и его размер size.
Функция сортирует массив a методом вставки. Метод вставки заключается в том, что каждый элемент вставляется на правильное место в уже отсортированной части массива.
Первый проход сортировки начинается с индекса 1 и до size-1. Значение tmp инициализируется значением a[i].
Затем происходит поиск подходящего места для tmp в уже отсортированной части массива. Для этого используется вложенный цикл, который начинается с i-1 и продолжается до 0, пока не будет найдено подходящее место или пока не будут просмотрены все элементы перед tmp.
Во время каждого прохода внешнего цикла, временная переменная tmp заменяется на значение a[i].
Если внутренний цикл завершается без нахождения подходящего места, это означает, что tmp меньше или равен каждому элементу перед ним. В этом случае tmp вставляется на свою позицию, а внутренний цикл прерывается.
Значение tmp заменяется на значение a[i], и внутренний цикл возобновляется с предыдущей итерации внешнего цикла.
В конце каждого прохода, tmp будет находиться на своем окончательном месте.
После завершения всех проходов, массив a будет отсортирован.
В данном коде сортировка вставками применяется к целочисленному массиву.
Временная переменная tmp используется для хранения текущего элемента, который вставляется в отсортированную часть массива.
Вложенный цикл используется для поиска подходящего места для текущего элемента в отсортированной части массива.
Если текущий элемент меньше или равен каждому элементу перед ним, он вставляется на свою позицию.
Значение tmp заменяется на значение a[i], и поиск подходящего места возобновляется с предыдущей итерации внешнего цикла.
В конце каждого прохода, tmp будет находиться на своем окончательном месте.
В конце функции возвращается отсортированный массив a.
В данном коде не используется дополнительная память, поэтому его сложность равна O(n^2), где n - размер массива.
Данный код не обрабатывает ошибки, такие как деление на ноль или переполнение.
Данный код не оптимизирован для больших массивов, так как его сложность квадратична по размеру массива.