Сортировка методом прямого включения

Такой метод широко используется при игре в карты. Элементы мысленно делятся на уже «готовую» последовательность а₁…а_i-1 и исходную последовательность а_i…а_n. При каждом шаге, начиная с i=1 и увеличивая i каждый раз на единицу, из исходной последовательности извлекается i-й элемент и перекладывается в готовую последовательность, при этом он вставляется в нужное место.

Ход сортировки массива {44, 55, 12, 42, 94, 18, 6, 67} методом прямого включения показан на рисунке 19.

Метод сортировки	Пример [программа pr_16]
for(i=1; i<N; i++) { vsp = a[i]; for(j=i-1; vsp<a[j]&&j>=0; j--) a[j+1] = a[j]; a[j+1] = vsp; }	Рисунок 20. Пример сортировки методом прямого включения

В реальном процессе поиска подходящего места удобно, чередуя сравнения и движения по последовательности, как бы просеивать х, то есть х сравнивается с очередным элементом a_j, а затем либо х вставляется на свободное место, либо a_j сдвигается вправо, и процесс «уходит» влево. Обратите внимание, что процесс просеивания может закончиться при выполнении одного из двух следующих условий:

1. найден элемент a_j со значением, меньшим, чем значение у х;

2. достигнут левый конец готовой последовательности.

Такой типичный случай повторяющегося процесса с двумя условиями окончания позволяет нам воспользоваться хорошо известным приемом барьера (sentinel). Здесь его легко применить, поставив барьер a₀со значением x.

Дата добавления: 2014-01-20