Сортировка вставкой

¹ : В лучшем случае достигается линейная сложность, например, если массив отсортирован по возрастанию.

Алгоритм

Сортировка вставкой чем-то похожа игру в карты, мы добавляем элемент к чему-то уже отсортированному.

Имеющийся массив надо условно разбить на отсортированную часть и неотсортированную, а потом добавлять по одному элементу к отсортированной части, вставляя его в нужное место

Преимущества алгоритма

1. Не используется дополнительная память.
2. Лёгкий для понимания и воспроизведения алгоритм.
3. Эффективен для маленьких массивов.

Недостатки алгоритма

Сложность в среднем и худшем случаях — $O(n^2)$

Реализация алгоритма

void insertionSort(int* a, int size) {
  for (int i = 1; i < size; i++) {
    int j = i - 1;
    int key = a[i];
    while (j >= 0 && a[j] > key) {
      arr[j + 1] = a[j];
      j--;
    }
    a[j + 1] = key;
  }
}

Запуск функции сортировки insertionSort(array, size);

Ввод

4 1 2 5 4 -68

Работа алгоритма

1. Берём 4 как элемент уже отсортированного массива: { 4 }
2. Добавляем к нему 1: 1 < 4, значит, ставим его до 4: { 1 4 }
3. Аналогично добавляем 2: { 1 2 4 }
4. Добавляем 5: 5 > 1, 5 > 2, 5 > 4, значит, ставим его после 4: { 1 2 4 5 }
5. Добавляем 4: 4 > 1, 4 > 2, 4 > 4 == false, значит, ставим его после 2 и до 4: { 1 2 4 4 5 }
6. Аналогично для -68

Вывод

-68 1 2 4 4 5