Сортировка вставкой
Теперь рассмотрим сортировку вставкой. Она основана на том, что если хвост списка уже отсортирован, то достаточно поставить первый элемент списка на его место в хвосте, и весь список будет отсортирован. При реализации этой идеи создадим два предиката.
Задача предиката 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 */
