在Prolog中对列表进行排序

Question

Prolog具有处理事物的独特方式，特别是因为几乎每个操作都涉及某种或另一种递归。

每种语言的经典示例之一是将整数列表按升序排序。

什么是最优方法（当然，不使用过多的内置谓词，当然排除了一个sort/2谓词）来对随机整数列表进行排序？

Answer 1

RomanBarták的Prolog编程站点给出examples of different sort algorithms，以优化的快速排序结束。

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

据我所知直接在Prolog中编写的最好的排序算法，没有参考任何特殊的内置插件使用某种形式的合并排序。

频繁的优化是开始合并不与长度为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|_] 
... 

注意，在Prolog的是直截了当地都在开始和结束时延长的列表。

因此，我们必须仅合并[1,2,3,4,5,6,7]和[2]。

使用Richard O'Keefe的原始实现（〜1984）的当前系统是Ciao-Prolog的 ciao-1.15/lib/sort.pl。