Prolog Quicksort 使用第二个元素作为枢轴 [英] Prolog Quicksort using second element as a pivot
问题描述
我一直在尝试学习 prolog,我想使用列表的第二个元素作为快速排序的枢轴.
I've been trying to learn prolog and I want to use the second element of a list as the pivot of a quicksort.
我想用 [Head |[枢轴|Tail] ] 作为方法中的输入会起作用,但是我不确定我可以在哪里放置Head",即第一个元素.
I thought using [Head | [Pivot | Tail] ] as the input in the method would work, but then I was not sure where I could place "Head", the first element.
像这样:
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) 对列表进行排序时.
它只是返回假.我做错了什么?
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([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?
最终,该算法将调用带有 exactly one 元素的列表,而您没有定义与该列表匹配的 qsort/2
子句.
Eventually this algorithm will make calls with a list with exactly one element, and you did not define a qsort/2
clause that will match with that list.
您可以通过添加规则来解决此问题:
You can resolve this by adding a rule:
qsort([],[]).
qsort([X], [X]).
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 Quicksort 使用第二个元素作为枢轴的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!