在Prolog中对列表进行排序

Question

Prolog有一种独特的处理方式,特别是因为几乎每个操作都涉及到这种或那种的递归.

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

什么是最佳方式(不使用太多内置谓词,当然排除了sort/2谓词)来排序随机的整数列表？

Answer 1

RomanBarták的Prolog编程站点提供了不同排序算法的示例,以优化的快速排序结束.

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]只有.

使用理查德奥基夫的原始实现(〜1984)的电流系统是侨-的Prolog在 ciao-1.15/lib/sort.pl.