Неизвестно - Prolog

Пусть

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

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

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

Найти в Списдва смежных элемента Х и 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 2 . Поэтому для длинных списков значительно лучше работает алгоритм быстрой сортировки , основанный на следующей идее (рис. 9.1):

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

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

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

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

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

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

разбиение( X, L, Больш, Меньш).

Временная сложность нашего алгоритма зависит от того, насколько нам повезет при разбиении сортируемого списка. Если списки всегда разбиваются на два списка примерно равной длины, то процедура сортировки имеет временную сложность порядка n log n , где n - длина исходного списка. Если же, наоборот, разбиение всегда приводит к тому, что один из списков оказывается значительно больше другого, то сложность будет порядка n 2 . Анализ показывает, что, к счастью, средняя производительность быстрой сортировки ближе к лучшему случаю, чем к худшему.