Prolog

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

        больше( X, Y)

означающее, что Х больше, чем 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  в упорядоченный хвост, поместив ее в такое место, чтобы получившийся список остался упорядоченным. Список отсортирован.