Prolog Quicksort使用第二个元素作为枢轴 [英] Prolog Quicksort using second element as a pivot

问题描述

我一直在尝试学习序言，我想将列表的第二个元素用作快速排序的关键.

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 | [枢纽|尾]]作为方法中的输入可以使用，但是后来我不确定在哪里可以放置"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).对列表进行排序时，它只是返回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([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子句.

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屋！