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