На этом шаге мы рассмотрим этот метод сортировки.
- Определение [1, с.33].
- Сортировка вставками - это название группы методов сортировки, основанных на последовательной вставке новых элементов в увеличивающийся упорядоченный список.
Среди методов сортировки вставками имеются три метода:
- линейная вставка,
- центрированная вставка и
- двоичная вставка,
Простейшим методом является линейная вставка. В этом методе уже существующий список рассматривается как линейный список, просматриваемый поэлементно, пока не будет найдена соответствующая позиция для нового элемента.
Линейная вставка обычно используется тогда, когда процесс, внешний к данной сортировке, динамически вносит добавления в список, все элементы которого известны и который должен поддерживаться в упорядоченном состоянии. Сортировка выполняется каждый раз при получении нового элемента, размещая этот элемент в нужное место списка.
Приведем несколько демонстрационных примеров.
-- Демонстрация сортировки элементов линейного списка -- методом линейной вставки (включения) -- ************************************ -- Функция, сортирующая список lst -- (с использованием охраняющих выражений) ------------------------------------------ sortIns:: [Int] -> [Int] sortIns lst | null lst = lst | True = insert (head lst) (sortIns (tail lst)) --------------------------------------------------------- -- Функция, добавляющая элемент x в упорядоченный по воз- -- растанию список lst с сохранением упорядоченности ---------------------------------------------------- insert:: Int -> [Int] -> [Int] insert x lst | null lst = [x] | x<=head lst = x : lst | True = head lst : insert x (tail lst) -- ******************************************************** -- Функция, сортирующая заданный список -- (с использованием сопоставления с образцом) ---------------------------------------------- iSort:: [Int] -> [Int] iSort [] = [] iSort (a:x) = ins a (iSort x) where ins a [] = [a] ins a (b:y) | a<=b = a : b : y | True = b : ins a y -- *************************************** -- Неудачные тестовые примеры: ----------------------------------------------------- test1 = sortIns [5,4,3,2,1,6] == [1,2,3,4,5,6] && sortIns (reverse [1..300]) == [1..300] ------------------------------------------------ test2 = insert 5 [] == [5] && insert 5 [1,3..12] == [1,3,5,5,7,9,11] -------------------------------------------------------- test3 = iSort [4,3,2,5,4,6,7] == [2,3,4,4,5,6,7] && iSort [7,6,5,4,3,2,1] == [1,2,3,4,5,6,7]
(1)Лорин Г. Сортировка и системы сортировки. - М.: Наука, 1983. - 384 с.
На следующем шаге мы рассмотрим сортировку выбором.
