Сортировка вставками
Один из простейших способов отсортировать массив - сортировка вставками.
В обычной жизни мы сталкиваемся с этим методом при игре в карты.
Чтобы отсортировать имеющиеся у вас карты, вы вынимаете карту,
сдвигаете оставшиеся карты, а затем вставляете карту на нужное место.
Процесс повторяется до тех пор, пока хоть одна карта не на месте.
Как среднее, так и худшее время для этого алгоритма - O(n2).
Дальнейшую информацию можно получить в книжке
Кнута [1998].
Теория
На рис.2.1(a) мы вынимаем элемент 3. Затем элементы, расположенные выше,
сдвигаем вниз - до тех пор, пока не найдем место, куда нужно вставить 3.
Это процесс продолжается на рис.2.1(b) для числа 1.
Наконец, на рис.2.1(c) мы завершаем сортировку, поместив 2 на нужное место.
Если длина нашего массива равна n, нам нужно пройтись по n - 1 элементам.
Каждый раз нам может понадобиться сдвинуть n - 1 других элементов,
получая алгоритм с временем работы O(n2).
Сортировка вставками относится к числу методов сортировки по месту.
Другими словами, ей не требуется вспомогательная память,
мы сортируем элементы массива, используя только память,
занимаемую самим массивом. Кроме того, она является устойчивой -
если среди сортируемых ключей имеются одинаковые, после сортировки
они остаются в исходном порядке.
Реализация
Реализацию сортировки вставками на Си вы найдете в разделе 4.1.
Оператор typedef T и оператор сравнения compGT следует изменить так,
чтобы они соответствовали данным, хранимым в таблице.
