Сортировка списков. Пример. Создадим предикат, позволяющий вычислить сумму элементов списка.

DOMAINS

listI = integer*

Пример. Создадим предикат, позволяющий вычислить сумму элементов списка.

sum([], 0). /* сумма элементов пустого списка равна

нулю */

sum([H|T], S) :–

sum(T, S_T), /* S_T — сумма элементов хвоста */

S = S_T + H. /* S — сумма элементов исходного

списка */

Пример. Напишем предикат, вычисляющий среднее арифметическое элементов списка.

avg(L,A):–

summa(L,S), /* помещаем в переменную S сумму

элементов списка */

length(L,K), /* переменная K равна количеству

элементов списка */

A=S/K. /* вычисляем среднее как отношение суммы

к количеству */

Пример. Создадим предикат, находящий минимальный элемент списка.

min_list([X],X). /* единственный элемент одноэлементного

списка является минимальным элементом

списка */

min_list([H|T],M):–

min_list(T,M_T), /* M_T — минимальный элемент хвоста */

min(H,M_T,M). /* M — минимум из M_T и первого элемента

исходного списка */

Пузырьковая сортировка: на каждом шаге сравниваются два соседних элемента, если стоят неправильно, то они меняются местами. Продолжаем процесс, пока есть пара соседних элементов, расположенных в неправильном порядке.

permutation([X,Y|T],[Y,X|T]):–

X>Y,!.

/* переставляем первые два

элемента, если первый больше

второго */

permutation([X|T],[X|T1]):–

permutation(T,T1).

/*переходим к перестановкам

в хвосте*/

bubble(L,L1):–

permutation(L,LL), /* вызываем предикат,

осуществляющий перестановку */

!,

bubble(LL,L1). /* пытаемся еще раз отсортировать

полученный список */

bubble(L,L). /* если перестановок не было, значит список

отсортирован */

Сортировка вставкой: основана на том, что если хвост списка уже отсортирован, то достаточно поставить первый элемент списка на его место в хвосте и весь список будет отсортирован.

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 */

Сортировка выбором: в списке находим минимальный элемент, используя предикат min_list, удаляем его из списка при помощи предиката delete_one.

delete_one(_,[],[]).

delete_one(X,[X|L],L):–!.

delete_one(X,[Y|L],[Y|L1]):–

delete_one(X,L,L1)

После удаления оставшийся список сортируем, и предписываем минимальный элемент в качестве головы к отсортированному списку.

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

остается пустым списком */

choice(L,[X|T]):– /* приписываем X (минимальный элемент

списка L) к отсортированному

списку T */

min_list(L,X), /* X — минимальный элемент

списка L */

delete_one(X,L,L1),

/* L1 — результат удаления

первого вхождения

элемента X из списка L */

choice(L1,T). /* сортируем список L1,

результат обозначаем T */

Быстрая сортировка (Сортировка Хоара): выбирается некоторый барьерный элемент, относительно которого разбиваем исходный список на два подсписка. В первом элементы меньше барьерного, во второй большие или равные. Каждый из списков сортируем тем же способом. Затем приписываем к списку элементов меньше барьерного, сам барьерный элемент и список элементов не меньше барьерного. В итоге получаем список из элементов, стоящих в правильном порядке.

Вспомогательный предикат partition будет отвечать за разбиение списка на два подсписка. У него будет четыре аргумента. Первые два элемента — входные: первый — исходный список, второй — барьерный элемент. Третий и четвертый элементы — выходные, соответственно, список элементов исходного списка, которые меньше барьерного, и список, состоящий из элементов, которые не меньше барьерного элемента.

Предикат quick_sort будет реализовывать алгоритм быстрой сортировки Хоара. Он будет состоять из двух предложений. Правило будет осуществлять с помощью предиката partition разделение непустого списка на два подсписка, затем сортировать каждый из этих подсписков рекурсивным вызовом себя самого, после чего, используя предикат conc (созданный нами ранее), конкретизирует второй аргумент списком, получаемым объединением отсортированного первого подсписка и списка, сконструированного из барьерного элемента (головы исходного списка) и отсортированного второго подсписка.

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

остается пустым списком */

quick_sort([H|T],O):–

partition(T,H,L,G),

/* делим список T на L (список

элементов меньших барьерного

элемента H) и G (список

элементов не меньших H) */

quick_sort(L,L_s),

/* список L_s — результат

упорядочивания элементов

списка L */

quick_sort(G,G_s),

/* аналогично, список G_s —

результат упорядочивания

элементов списка G */

conc(L_s,[H|G_s],O).

/* соединяем список L_s со

списком, у которого голова H,

а хвост G_s, результат

обозначаем O */

partition([],_,[],[]). /* как бы мы ни делили элементы

пустого списка, ничего кроме

пустых списков не получим */

partition([X|T],Y,[X|T1],Bs):–

X<Y,!,

partition(T,Y,T1,Bs).

/* если элемент X меньше барьерного

элемента Y, то мы добавляем его

в третий аргумент */

partition([X|T],Y,T1,[X|Bs]):–

partition(T,Y,T1,Bs).

/* в противном случае дописываем

его в четвертый аргумент */

Сортировка слияниями: разобьем список, который нужно упорядочить, на два подсписка. Упорядочим каждый из них тем же методом, после чего сольем упорядоченный подсписки обратно в один общий список. Этот метод придумал Фон Нейман в 1945 году. Потребуются вспомогательные предикаты.

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

splitting([],[],[])./* пустой список можно расщепить

только на пустые подсписки */

splitting([H],[H],[]). /* одноэлементный список разбиваем

на одноэлементный список

и пустой список */

splitting([H1,H2|T],[H1|T1],[H2|T2]):–

splitting(T,T1,T2).

/* элемент H1 отправляем в первый

подсписок, элемент H2 — во второй

подсписок, хвост T разбиваем

на подсписки T1 и T2 */

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

fusion_sort([],[]):–!./* отсортированный пустой список

остается пустым списком */

fusion_sort([H],[H]):–!. /* одноэлементный список

упорядочен */

fusion_sort(L,L_s):–

splitting(L,L1,L2),

/* расщепляем список L на два

подсписка */

fusion_sort(L1,L1_s),

/* L1_s — результат сортировки

L1 */

fusion_sort(L2,L2_s),

/* L2_s — результат сортировки

L2 */

fusion(L1_s,L2_s,L_s).

/* сливаем L1_s и L2_s

в список L_s */

Как проверить, отсортирован ли список?

sorted([ ]). /* пустой список отсортирован */

sorted([_])./* одноэлементный список упорядочен */

sorted([X,Y|T]):–

X<=Y,

sorted([Y|T]).

/* список упорядочен, если первые

два элемента расположены

в правильном порядке и список,

образованный вторым элементом

и хвостом исходного, упорядочен */