Prolog

Неизвестно

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

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

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

Пусть

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

обозначает отношение, в котором Спис–

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

получившийся список остался упорядоченным. Список отсортирован.

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

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

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

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

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

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

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

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

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

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

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

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

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

(1) Удалить из списка L какой-нибудь элемент Х и разбить оставшуюся часть на два списка, называемые Меньш и Больш, следующим образом: все элементы большие, чем X, принадлежат списку Больш, остальные - списку Меньш.

(2) Отсортировать список Меньш, результат - список УпорМеньш.

(3) Отсортировать список Больш, результат - список УпорБольш.

(4) Получить результирующий упорядоченный список как конкатенацию списков УпорМеньш и [ Х | УпорБольш].

Заметим, что если исходный список пуст, то результатом сортировки также будет пустой список. Реализация быстрой сортировки на Прологе показана на рис. 9.2. Здесь в качестве элемента X, удаляемого из списка, всегда выбирается просто голова этого списка. Разбиение на два списка запрограммировано как отношение с четырьмя аргументами: