Второй метод называется метод вставок., т.к. на j-ом этапе мы "вставляем" j-ый элемент M[j]в нужную позицию среди элементов M[1], M[2],. . ., M[j-1], которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены.
Сказанное можно записать следующим образом:
нц для j от 2 до N
переместить M[j] на позицию i <= j такую, что
M[j] < M[k] для i<= k < j и
либо M[j] >= M[i-1], либо i=1
кц
Чтобы сделать процесс перемещения элемента M[j], более простым, полезно воспользоваться барьером: ввести "фиктивный" элемент M[0], чье значение будет заведомо меньше значения любого из "реальных"элементов массива (как это можно сделать?). Мы обозначим это значение через —оо.
Если барьер не использовать, то перед вставкой M[j], в позицию i-1 надо проверить, не будет ли i=1. Если нет, тогда сравнить M[j]( который в этот момент будет находиться в позиции i) с элементом M[i-1].
Описанный алгоритм имеет следующий вид:
| begin M[0] := -oo; for j:=2 to N do begin i := j; while M[i] < M[i-1] do begin swap(M[i],M[i-1]); i := i-1 end end end;
|
Процедура swap нам уже встречалась.
Демонстрация сортировки вставками.
