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

Один из простейших способов отсортировать массив - сортировка вставками. В обычной жизни мы сталкиваемся с этим методом при игре в карты. Чтобы отсортировать имеющиеся в вас карты, вы вынимаете карту, сдвигаете оставшиеся карты, а затем вставляете карту на нужное место. Процесс повторяется до тех пор, пока хоть одна карта находится не на месте. Как среднее, так и худшее время для этого алгоритма - О(п2). Дальнейшую информацию можно получить в книжке Кнута

Теория

На рис.2.2(а) мы вынимаем элемент 3. Затем элементы, расположенные выше, сдвигаем вниз - до тех пор, пока не найдем место, куда нужно вставить 3. Это процесс продолжается на рис.Рис. 0.1(Ь) для числа 1. Наконец, на рис.2.1 (с) мы завершаем сортировку, поместив 2 на нужное место. Если длина нашего массива равна п, нам нужно пройтись по п - 1 элементам. Каждый раз нам может понадобиться сдвинуть п - 1 других элементов. Вот почему этот метод требует довольно-таки много времени.

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

Реализация

Реализацию сортировки вставками на Си вы найдете в разделе 4.1. Оператор ІуреіІеГ Т и оператор сравнения сошрОТ следует изменить так, чтобы они соответствовали данным, хранимым в таблице.