序言：使用最後一個元素作爲主軸的快速排序（無限循環）

Question

我想在Prolog中使用最後一個元素作爲主軸來實現Quicksort，但不知何故我的謂詞進入了一個無限循環。我使用累加器來確定到目前爲止排序的部分（最後應該與它應該查找的排序列表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

回答;然而請將原始版本與「最後一個元素作爲數據透視」版本進行比較，你會看到「最後一個元素作爲數據透視」是愚蠢的。是否有可能在問題陳述的某個地方出現了我們都沒有找到的地方？

---

在我看來，如果您使用一個更簡單的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實施只是有點：

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

所以你：

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

你已經在quicksort//1頭解壓的第一個值可以直接使用

list_front_last(Xs, X, Front, Pivot) 

而不是呼叫append/3。