Сортировка простыми вставками
Самый простой способ сортировки2), который приходит в голову, - это упорядочение данных по мере их поступления. В этом случае при вводе каждого нового значения можно опираться на тот факт, что все предыдущие элементы уже образуют отсортированную последовательность.
Алгоритм ПрВст
- Первый элемент записать "не раздумывая".
- Пока не закончится последовательность вводимых данных, для каждого нового ее элемента выполнять следующие действия:
- начав с конца уже существующей упорядоченной последовательности, все ее элементы, которые больше, чем вновь вводимый элемент, сдвинуть на 1 шаг назад;
- записать новый элемент на освободившееся место.
При этом, разумеется, можно прочитать все вводимые элементы одновременно, записать их в массив, а потом "воображать", что каждый очередной элемент был введен только что. На суть и структуру алгоритма это не повлияет.
Реализация алгоритма ПрВст
for i:= 2 to N do if a[i-1]>a[i] then {*} begin x:= a[i]; j:= i-1; while (j>0)and(a[j]>x) do {**} begin a[j+1]:= a[j]; j:= j-1; end; a[j+1]:= x; end;
Метод прямых вставок с барьером (ПрВстБар)
Для того чтобы сократить количество сравнений, производимых нашей программой, дополним сортируемый массив нулевой компонентой (это следует сделать в разделе описаний var) и будем записывать в нее поочередно каждый вставляемый элемент (сравните строки {*} и {**} в приведенных вариантах программы). В тех случаях, когда вставляемое значение окажется меньше, чем a[1], компонента a[0] будет работать как "барьер", не дающий индексу j выйти за нижнюю границу массива. Кроме того, компонента a[0] может заменить собою и дополнительную переменную х:
for i:= 2 to N do if a[i-1]>a[i] then begin a[0]:= a[i]; {*} j:= i-1; while a[j]>a[0] do {**} begin a[j+1]:= a[j]; j:= j-1; end; a[j+1]:= a[0]; end;
Эффективность алгоритма ПрВстБар
Понятно, что для этой сортировки наилучшим будет случай, когда на вход подается уже упорядоченная последовательность данных. Тогда алгоритм ПрВстБар совершит N-1 сравнение и 0 пересылок данных.
В худшем же случае - когда входная последовательность упорядочена "наоборот" - сравнений будет уже (N+1)*N/2, а пересылок (N-1)*(N+3). Таким образом, этот алгоритм имеет сложность ~N2 (читается "порядка эн квадрат") по обоим параметрам.
Пример сортировки
Предположим, что нужно отсортировать следующий набор чисел:
5 3 4 3 6 2 1
Выполняя алгоритм ПрВстБар, мы получим такие результаты (подчеркнута уже отсортированная часть массива, полужирным выделена сдвигаемая последовательность, а квадратиком выделен вставляемый элемент):
Состояние массива Сдвиги Сравнения Пересылки данных0 шаг: 5343621 1 шаг: 5343621 1 1+13) 1+24)
2 шаг: 3543621 1 1+1 1+2 3 шаг: 3453621 2 2+1 2+2 4 шаг: 3345621 0 1 0 5 шаг: 3345621 5 5+1 5+2 6 шаг: 2334561 6 6+1 6+2 Результат: 1233456 15 20 25
