我一直在尝试学习序言,我想使用列表的第二个元素作为快速排序的枢轴。
我想使用[Head | [枢轴| Tail] ] 作为方法中的输入可以工作,但后来我不确定可以在哪里放置第一个元素“Head”。
像这样:
qsort([],[]):- !.
qsort([Head|[Pivot|Tail]],Sorted):-
split(Pivot,[Head|Tail],Less,Greater),
qsort(Less,SortedLess),
qsort(Greater,SortedGreater),
append(SortedLess,[Pivot|SortedGreater],Sorted).
split(_,[],[],[]).
split(Pivot,[X|T],[X|Less],Greater):-
X=<Pivot,split(Pivot,T,Less,Greater).
split(Pivot,[X|T],Less,[X|Greater]):-
X>Pivot,split(Pivot,T,Less,Greater).
但是,当我尝试使用 qsort([8, 3, 4, 12, 25, 4, 6, 1, 9, 22, 6], Sorted) 对列表进行排序时。
简单地返回 false。我做错了什么?
最佳答案
However, when I try to sort the list with
qsort([8, 3, 4, 12, 25, 4, 6, 1, 9, 22, 6], Sorted)
. It simply returns false. What am I doing wrong?
最终,该算法将使用包含恰好一个元素的列表进行调用,并且您没有定义与该列表匹配的qsort/2
子句。
您可以通过添加规则来解决此问题:
qsort([],[]).
<b>qsort([X], [X]).</b>
qsort([Head, Pivot|Tail],Sorted):-
split(Pivot,[Head|Tail],Less,Greater),
qsort(Less,SortedLess),
qsort(Greater,SortedGreater),
append(SortedLess,[Pivot|SortedGreater],Sorted).
这给了我们:
?- qsort([8, 3, 4, 12, 25, 4, 6, 1, 9, 22, 6], Sorted).
Sorted = [1, 3, 4, 4, 6, 6, 8, 9, 12|...] ;
false.
关于使用第二个元素作为基准的 Prolog 快速排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59227028/