Сортировка вставками в языке Си

Привет, сегодня поговорим про сортировка вставками в языке си, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое сортировка вставками в языке си , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

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

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

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

/* Сортировка вставками. Об этом говорит сайт https://intellect.icu  . */
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]Т.е. устойчив.

На этом все! Теперь вы знаете все про сортировка вставками в языке си, Помните, что это теперь будет проще использовать на практике. Надеюсь, что теперь ты понял что такое сортировка вставками в языке си и для чего все это нужно, а если не понял, или есть замечания, то не стесняйся, пиши или спрашивай в комментариях, с удовольствием отвечу. Для того чтобы глубже понять настоятельно рекомендую изучить всю информацию из категории Алгоритмы и теория алгоритмов