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

Сортировка представляет собой переупорядочение элементов списка определенным образом. Назначением сортировки является упрощение доступа к нужным элементам. Для сортировки списков обычно применяются три метода:

· метод перестановки,

· метод вставки,

· метод выборки.

Также можно использовать комбинации указанных методов.

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

Второй из методов, метод вставки, особенно удобен для реализации на Прологе.

Пример 10: сортировка списков методом вставки.

domains

list=integer*

predicates

insert_sort (list, list)

insert (integer, list, list)

asc_order (integer, integer)

clauses

insert_sort ( [], []).

insert_sort ([H1|T1], L2):- insert_sort (T1, T2),

insert(H1, T2, L2).

insert (X, [H1| T1], [H1| T2]) :- asc_order (X, H1), !,

insert (X, T1, T2).

insert (X, L1, [X| L1]).

asc_order (X, Y):- X>Y.

goal

insert_sort ([4, 7, 3, 9], L).

Для удовлетворения первого правила оба списка должны быть пустыми. Для того, чтобы достичь этого состояния, по второму правилу происходит рекурсивный вызов предиката insert_sort, при этом значениями H1 последовательно становятся все элементы исходного списка, которые затем помещаются в стек. В результате исходный список становится пустым и по первому правилу выходной список также становится пустым.

После того, как произошло успешное завершение первого правила, Пролог пытается выполнить второй предикат insert, вызов которого содержится в теле второго правила. Переменной H1 сначала присваивается первое взятое из стека значение 9, а предикат принимает вид insert (9, [], [9]).

Так как теперь удовлетворено все второе правило, то происходит возврат на один шаг рекурсии в предикате insert_sort. Из стека извлекается 3 и по третьему правилу вызывается предикат asc_order, то есть происходит попытка удовлетворения пятого правила asc_order (3, 9):- 3>9. Так как данное правило заканчивается неуспешно, то неуспешно заканчивается и третье правило, следовательно, удовлетворяетсячетвертое правило и 3 вставляется в выходной список слева от 9: insert (3, [9], [3, 9]).

Далее происходит возврат к предикату insert_sort, который принимает следующий вид: insert_sort ([3, 9], [3, 9]).

На следующем шаге рекурсиииз стека извлекается 7 и по третьему правилу вызывается предикат asc_order в виде asc_order (7, 3):- 7>3. Так как данное правило заканчивается успешно, то элемент 3 убирается в стек и insert вызвается рекурсивно еще раз, но уже с хвостом списка – [9]: insert (7, [9], _). Так как правило asc_order (7, 9):- 7>9 заканчивается неуспешно, то выполняется четвертое правило, происходит возврат на предыдущие шаги рекурсии сначала insert, затем insert_sort.

В результате 7 помещается в выходной список между элементами 3 и 9: insert (7, [3, 9], [3, 7, 9]).

При возврате еще на один шаг рекурсиииз стека извлекается 4 и по третьему правилу вызывается предикат asc_order в виде asc_order (4, 3):- 4>3. Так как данное правило заканчивается успешно, то элемент 3 убирается в стек и insert вызвается рекурсивно еще раз, но уже с хвостом списка – [7, 9]: insert (4, [7, 9], _). Так как правило asc_order (4, 7):- 4>7 заканчивается неуспешно, то выполняется четвертое правило, происходит возврат на предыдущие шаги рекурсии сначала insert, затем insert_sort.

В результате 4 помещается в выходной список между элементами 3 и 7:

insert (4, [3, 7, 9], [3, 4, 7, 9]).

insert_sort [4, 7, 3, 9], [3, 4, 7, 9]).