о чем уже говорилось в гл. 3. Список
[alpha,beta,gamma] упорядочен в алфавитном порядке, поскольку каждая пара соседних атомов этого списка удовлетворяет предикату
меньше.Специалисты по информатике разработали много методов сортировки списков, когда задан некоторый предикат, который говорит нам о том, находятся ли соседние элементы списка в требуемом порядке следования. Мы рассмотрим Пролог-программы для четырех таких методов: наивная сортировка, сортировка включением (вставками), сортировка методом пузырька и быстрая сортировка. В каждой программе используется предикат упорядочено, который может быть определен через '‹' меньше или любой другой предикат по вашему усмотрению, в зависимости от того, какого рода структуры вы сортируете. При этом предполагается, что целевое утверждение упорядочено(Х, Y) доказуемо, если объекты X и Y удовлетворяют требуемому порядку следования, т. е. если X в некотором смысле меньше чем Y.
Один из способов сортировки чисел в порядке возрастания состоит в следующем: вначале создается некоторая перестановка чисел, затем проверяется расположен ли полученный список в порядке возрастания. Если это не так, то создается новая перестановка чисел. Этот метод известен под названием наивная сортировка:
наивсорт(L1,L2):- перестановка(L1,L2),отсортировано(L2),!.
перестановка(L,[H|T]):-присоединить(V,[Н|U],L), присоединить(V,U,W), перестановка(W,Т).
перестановка([],[]).
отсортировано(L):- отсортировано(0,L).
отсортировано(_,[]).
отсортировано(N,[H|T]):- упорядочено(N,Н),отсортировано(Н,T).
Используемый здесь предикат присоединить многократна определялся ранее. В этой программе предикаты имеют следующий смысл:
Наивсорт(L1, L2) означает, что L2 – это список, являющийся упорядоченной версией списка L1;
Перестановка(L1, L2) означает, что L2- это список, содержащий все элементы списка L1 в одном из многих возможных порядков их следования; в терминологии разд. 4.3 – это генератор.
Предикат отсортировано(L) означает, что числа в списке L упорядочены в порядке возрастания; это – 'контролер'.
Процесс поиска упорядоченной версии списка заключается в создании некоторой перестановки элементов и проверки ее упорядоченности. Если это так, то единственный ответ найден. Иначе мы вынуждены продолжать создание перестановок. Это не очень эффективный метод сортировки списка.
При сортировке включением каждый элемент списка рассматривается отдельно и включается в новый список на соответствующее место. Этот метод используется, например, при игре в карты, когда игрок сортирует имеющиеся на руках карты, вынимая и переставляя по одной карте за раз. Целевое утверждение
