Сортировка списка в Прологе

Question

В Прологе есть уникальный способ обработки вещей, тем более что практически каждая операция включает рекурсию того или иного рода.

Одним из классических примеров, которые есть в каждом языке, является сортировка списка целых чисел в порядке возрастания.

Каков оптимальный способ (без использования слишком большого количества встроенных предикатов, что, конечно, исключает предикат sort / 2) для сортировки случайного списка целых чисел?

Answer 1

Сайт Пролога Романа Бартака дает примеров различных алгоритмов сортировки , заканчивающихся оптимизированной быстрой сортировкой.

quick_sort2(List,Sorted):-q_sort(List,[],Sorted).
q_sort([],Acc,Acc).
q_sort([H|T],Acc,Sorted):-
    pivoting(H,T,L1,L2),
    q_sort(L1,Acc,Sorted1),q_sort(L2,[H|Sorted1],Sorted)

Answer 2

Насколько мне известно, лучшие алгоритмы сортировки, написанные непосредственно на Прологе, без ссылки на какие-либо специальные встроенные модули используют некоторую форму сортировки слиянием.

Частой оптимизацией является начало слияния не со списками длины 1, а с уже отсортированными сегментами.

То есть для сортировки списка [4,5,3,6,2,7,1,2] списки [4,5], [3,6], [2,7], [1,2] будут объединены.

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

[4,5|_]
[3,4,5|_]
[3,4,5,6|_]
...

Обратите внимание, что в Прологе просто расширить список как в начале, так и в конце.

Таким образом, мы должны объединить только [1,2,3,4,5,6,7] и [2].

Текущая система, в которой используется первоначальная реализация (~ 1984 г.) Ричарда О'Кифа: ​​ Ciao-Prolog в ciao-1.15/lib/sort.pl.