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