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

Теперь рассмотрим сортировку вставкой. Она основана на том, что если хвост списка уже отсортирован, то достаточно поставить первый элемент списка на его место в хвосте, и весь список будет отсортирован. При реализации этой идеи создадим два предиката.

Задача предиката insert — вставить значение (голову исходного списка) в уже отсортированный список (хвост исходного списка), так чтобы он остался упорядоченным. Его первым аргументом будет вставляемое значение, вторым — отсортированный список, третьим — список, полученный вставкой первого аргумента в нужное место второго аргумента так, чтобы не нарушить порядок.

Предикат ins_sort, собственно, и будет организовывать сортировку исходного списка методом вставок. В качестве первого аргумента ему дают произвольный список, который нужно отсортировать. Вторым аргументом он возвращает список, состоящий из элементов исходного списка, стоящих в правильном порядке.

ins_sort([ ], [ ]). /* отсортированный пустой список остается пустым списком */

ins_sort([H|T], L): –

ins_sort(T, T_Sort),

/* T — хвост исходного списка, T_Sort — отсортированный хвост исходного списка */

insert(H, T_Sort, L).

/* вставляем H (первый элемент исходного списка)в T_Sort, получаем L (список, состоящий из элементов исходного списка,

стоящих по неубыванию) */

insert(X, [], [X]). /* при вставке любого значения в пустой список, получаем одноэлементный список */

insert(X, [H|T], [H|T1]): – X> H,!, /* если вставляемое значение больше головы списка, значит его нужно вставлять в хвост */

insert(X, T, T1).

/* вставляем X в хвост T, в результате получаем список T1 */

insert(X, T, [X|T]). /* это предложение (за счет отсечения в предыдущем правиле) выполняется, только если вставляемое значение не больше головы списка T, значит, добавляем его первым элементом в список T */

⇐ Предыдущая 1 234 5 Следующая ⇒