Программирование на языке Пролог для искусственного интеллекта

L = а затем b затем ничего_не_делать

?-  преобр( [а, b, с], L, +, 0).

L = а+(b+(с+0) )

9.1.2. Сортировка списков

Сортировка применяется очень часто. Список можно отсортировать (упорядочить), если между его элементами определено отношение порядка. Для удобства изложения мы будем использовать отношение порядка

больше( X, Y)

означающее, что X больше, чем Y, независимо от того, что мы в действительности понимаем под "больше, чем". Если элементами списка являются числа, то отношение больше будет, вероятно, определено как

больше( X, Y) :- X > Y.

Если же элементы списка — атомы, то отношение больше может соответствовать алфавитному порядку между ними.

Пусть

сорт( Спис, УпорСпис)

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

Для того, чтобы упорядочить список Спис, необходимо:

• Найти в Спис два смежных элемента X и Y, таких, что больше( X, Y), и поменять X и Y местами, получив тем самым новый список Спис1; затем отсортировать Спис1.

• Если в Спис нет ни одной пары смежных элементов X и Y, таких, что больше( X, Y), то считать, что Спис уже отсортирован.

Мы переставили местами 2 элемента X и Y, расположенные в списке "не в том порядке", с целью приблизить список к своему упорядоченному состоянию. Имеется в виду, что после достаточно большого числа перестановок все элементы списка будут расположены в правильном порядке. Описанный принцип сортировки принято называть методом пузырька, поэтому соответствующая прологовская процедура будет называться пузырек.

пузырек( Спис, УпорСпис) :-

 перест( Спис, Спис1), !, % Полезная перестановка?

 пузырек( Спис1, УпорСпис).

пузырек( УпорСпис, УпорСпис).

  % Если нет, то список уже упорядочен

перест( [X, Y | Остаток], [Y, X ) Остаток] ):-

 % Перестановка первых двух элементов

 больше( X, Y).

перест( [Z | Остаток], [Z | Остаток1] ):-

 перест( Остаток, Остаток1). % Перестановка в хвосте

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

Для того, чтобы упорядочить непустой список L = [X | Хв], необходимо:

(1) Упорядочить хвост Хв списка  L.

(2) Вставить голову X списка L в упорядоченный хвост, поместив ее в такое место, чтобы получившийся список остался упорядоченным. Список отсортирован.

Этот алгоритм транслируется в следующую процедуру вставсорт на Прологе:

вставсорт([], []).

вставсорт( [X | Хв], УпорСпис) :-

 вставсорт( Хв, УпорХв), % Сортировка хвоста

встав( X, УпорХв, УпорСпис).

  % Вставить X на нужное место

встав( X, [Y | УпорСпис], [Y | УпорСпис1]):-

 больше( X, Y), !,

 встав( X, УпорСпис, УпорСпис1).

встав( X, УпорСпис, [X | УпорСпис] ).

Рис. 9.1. Сортировка списка процедурой быстрсорт.

Процедуры сортировки пузырек и вставсорт просты, но не эффективны. Из этих двух процедур процедура со вставками более эффективна, однако среднее время, необходимое для сортировки списка длиной  n  процедурой вставсорт, возрастает с ростом n пропорционально n². Поэтому для длинных списков значительно лучше работает алгоритм быстрой сортировки, основанный на следующей идее (рис. 9.1):