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

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

Начало       d c a b
Проход 1     c d a b
Проход 2     a c d b
Проход 3     a b c d

Пример реализации сортировки вставками показан ниже:

/* Сортировка вставками. */
void insert(char *items, int count)
{

  register int a, b;
  char t;

  for(a=1; a < count; ++a) {
    t = items[a];
    for(b=a-1; (b >= 0) && (t < items[b]); b--)
      items[b+1] = items[b];
    items[b+1] = t;
  }
}

В отличие от пузырьковой сортировки и сортировки посредством выбора, количество сравнений в сортировке вставками зависит от изначальной упорядоченности списка. Если список уже отсортирован, количество сравнений равно n - 1; в противном случае его производительность является величиной порядка n².

Вообще говоря, в худших случаях сортировка вставками настолько же плоха, как и пузырьковая сортировка и сортировка посредством выбора, а в среднем она лишь немного лучше. Тем не менее, у сортировки вставками есть два преимущества. Во-первых, ее поведение естественно. Другими словами, она работает меньше всего, когда массив уже упорядочен, и больше всего, когда массив отсортирован в обратном порядке. Поэтому сортировка вставками — идеальный алгоритм для почти упорядоченных списков. Второе преимущество заключается в том, что данный алгоритм не меняет порядок одинаковых ключей^[1]. Это значит, что если список отсортирован по двум ключам, то после сортировки вставками он останется упорядоченным по обоим.

Несмотря на то, что количество сравнений при определенных наборах данных может быть довольно низким, при каждой вставке элемента на свое место массив необходимо сдвигать. Вследствие этого количество перемещений может быть значительным.

^[1]Т.е. устойчив.