programming-languages - 条件序言排序方法

Question

我是序言语言的新手。我在prolog中遇到了一个有趣的问题。

通常，快速排序适用于大型列表。但是对于较小的列表，插入排序比快速排序更有效。我如何在 Prolog 中编写一个最初使用快速排序的排序算法，但为 15 个或更少元素的子列表切换到插入排序。

提示是我们可以在分区操作期间计算元素的数量。但我不知道如何为这个问题形成一个算法。任何人都可以请指导/帮助。

提前非常感谢。

Answer 1

partition将每个元素放到一个或另一个子列表中。所以只需再维护两个参数，它们是子列表的计数，从 0 开始，并在将另一个元素添加到其子列表时增加相应的计数器：

part([]    ,[],[],0 ,0).
part([P|LS],L , R,CL,CR):- part(P,LS,L,[],R,[],0,CL,0,CR).

part(_,[]    ,LZ,LZ,RZ,RZ,CL,CL,CR,CR).
part(P,[X|LS],L ,LZ,R ,RZ,IL,CL,JR,CR):-
   X < P -> L=[X|T],I2 is IL+1, part(P,LS,T,LZ,R,RZ,I2,CL,JR,CR)
 ; .....

Answer 2

您可以为mysort根据列表长度选择算法的规则创建几个子句，如下所示：

mySort(In, Out) :-
    count(In, Cnt),
    Cnt < 15,
    insertionSort(In, Out).
mySort(In, Out) :-
    count(In, Cnt),
    Cnt >= 15,
    quickSort(In, Out).

quickSort(In, Out) :-
    partition(In, Left, Right),
    mySort(Left, SortedLeft),
    mySort(Right, SortedRight),
    mergeSorted(SortedLeft, SortedRight, Out).

诀窍是规则在对输入进行分区后quickSort/2引用sort，而不是。quickSort这意味着一旦计数低于 15，insertionSort将用于对较小的分区进行排序。