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

Объединение двух списков

Слияние двух списков и получение, таким образом, третьего списка принадлежит к числу наиболее полезных при работе со списками операций. Обозначим первый список L1, а второй список - L2. Пусть L1 = [1, 2, 3], а L2 = [4, 5]. Предикат append присоединяет L2 к L1 и создает выходной список L3, в который он должен переслать все элементы L1 и L2. Весь процесс можно представить следующим образом:

1. Список L3 вначале пуст.

2. Элементы списка L1 пересылаются в L3, теперь значением L3 будет [1, 2, 3].

3. Элементы списка L2 пересылаются в L3, в результате чего тот принимает значение [1, 2, 3, 4, 5].

Тогда программа на языке Турбо-Пролог имеет следующий вид:

Пример 37: объединение двух списков.

domains

list=integer*

predicates

аppend (list, list, list)

clauses

append ([], L2, L2).

append ([H|T1], L2, [H|T3 ]):- append (T1, L2, T3).

goal

append ([1, 2, 3], [4, 5], L3).

Основное использование предиката append состоит в объединении двух списков, что делается при помощи задания цели вида append ([1, 2, 3], [4, 5], L3). Поиск ответа на вопрос типа: append (L1, [3, 4, 5], [1, 2, 3, 4, 5]) – сводится к поиску такого списка L1=[1, 2], который при слиянии со списком L2 = [3, 4, 5] даст список L3 = [1, 2, 3, 4, 5]. При обработки цели append (L1, L2, [1, 2, 3, 4, 5]) ищутся такие списки L1 и L2, что их объединение даст список L3 = [1, 2, 3, 4, 5].

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

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

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

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

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

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

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

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

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]).

Дата добавления: 2015-06-27