Prolog：使用最后一个元素作为枢轴的快速排序（无限循环）

Question

我正在尝试使用最后一个元素作为基准在 Prolog 中实现快速排序，但不知何故我的谓词进入了无限循环。我正在使用累加器来确定到目前为止排序的部分（最后应该等于它应该寻找的排序列表 S）。

quicksort([], S, S).
quicksort(L, S, A ) :-
    lastElement(L, P), /*last element P as pivot*/
    split(L, P, Greater, Smaller), /* splits L into set Greater (than) and Smaller (than) by pivot P */
    quicksort(Greater, Greater_S, A), /* require Greater to be sorted as well, calling this Greater_S */
    quicksort(Smaller, S, [P|Greater_S]). /* same for Smaller, but accumulator should already have P and Greater_S sorted -> [P|Greater_S] as accumulator */

quicksort(L, S) :-
    quicksort(L, S, []).

不知何故，在 quicksort(G, G_S, A) 中，列表 G_S 似乎使用相同的元素迭代增加大小，即 [X, X, X, X, ...].

我做错了什么？

如果有人能帮助我，我将不胜感激！

提前致谢。

编辑：谓词的定义 split/4 和 lastElement/2:

lastElement([X], X). 
lastElement([_|T], X) :- lastElement(T, X). 

split([], _, [], []).
split([H|T], P, G, K) :-
    H > P,
    G = [H|T_],
    split(T, P, T_, K).
split([H|T], P, G, K) :-
    H =< P,
    K = [H|T_],
    split(T, P, G, T_).

Answer 1

在下面回答；但是请将原始版本与 "last element as pivot" 版本进行比较，您会发现 "last element as pivot" 很愚蠢。是否有可能我们都遗漏了问题陈述中的某处陷阱？

在我看来，如果您使用更简单的 Quicksort 实现作为起点，您的生活会更轻松。来自 Prolog wiki page

partition([], _, [], []).
partition([X|Xs], Pivot, Smalls, Bigs) :-
    (   X @< Pivot ->
        Smalls = [X|Rest],
        partition(Xs, Pivot, Rest, Bigs)
    ;   Bigs = [X|Rest],
        partition(Xs, Pivot, Smalls, Rest)
    ).

quicksort([])     --> [].
quicksort([X|Xs]) -->
    { partition(Xs, X, Smaller, Bigger) },
    quicksort(Smaller), [X], quicksort(Bigger).

您将不得不使用 phrase:

quicksort(List, Sorted) :- phrase(quicksort(List), Sorted).

所以现在排序：

?- quicksort([c,b,a,b], S).
S = [a, b, b, c].

唯一需要更改的是取最后一个元素而不是第一个元素，可能在 quicksort//1 的第二个子句中，如下所示：

quicksort([X|Xs]) -->
    {   append(Front, [Pivot], [X|Xs]),
        partition(Front, Pivot, Smaller, Bigger)
    },
    quicksort(Smaller), [Pivot], quicksort(Bigger).

这种append/3的用法留下了一个选择点；如果你愿意，你可以自己写 list_front_last/3，或者使用

once( append(...) )

希望对您有所帮助。

编辑：

您可以稍微更改 lastElement 的实现：

list_front_last([], Last, [], Last).
list_front_last([X|Xs], X0, [X0|Front], Last) :-
    list_front_last(Xs, X, Front, Last).

您已经解包了quicksort//1头部的第一个值：

quicksort([X|Xs]) --> ...

所以你可以直接使用

list_front_last(Xs, X, Front, Pivot)

而不是调用 append/3。

Prolog：使用最后一个元素作为枢轴的快速排序（无限循环）

Prolog: quicksort using last element as pivot (infinite loop)

prolog

quicksort