(И9)(И10) Сортировка

Посмотреть сортировку выбором

Посмотреть сортировку пузырьком

Сортировка вставками

Метод называется метод вставок, т.к. на 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].

Описанный алгоритм имеет следующий вид:

Демонстрация сортировки вставками
Процедура swap  - процедура обмена значениями двух переменных.