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

Question

I'm trying to implement Quicksort in Prolog using the last element as pivot but somehow my predicate gets into an infinite loop. I'm using an accumulator to determine the part sorted so far (which in the end should be equal to the sorted list S that it should be looking for).

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, []).

Somehow in quicksort(G, G_S, A), the list G_S seems to iteratively increase in size with the same element, i.e. [X, X, X, X, ...].

What am I doing wrong?

If anyone could help me out it'd be much appreciated!

Thanks in advance.

EDIT: Definitions of the predicates split/4 and 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_).

You remember that the last element in the first argument to deel/4 has the pivot as the last element, right? Anyway, what is this accumulator for, exactly? — user1812457
@Skyfe Sorry about the question, but why are you doing a) quicksort and b) using the last element? Both are poor choices, mainly because of how lists are represented in Prolog (basically, cons pairs). — user1812457
@Skyfe And btw, I looked at the wikipedia Prolog quicksort here; this does not use an accumulator; it uses normal tail recursion and difference lists. — user1812457

Unknown Unknown · Accepted Answer · 2017-04-13T11:02:13

Answer below; however please compare the original version to the "last element as pivot" version and you will see that "last element as pivot" is just silly. Is it possible that there is a gotcha somewhere in the problem statement that we are both missing?

It seems to me that your life will be easier if you used a simpler Quicksort implementation as a starting point. From the 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).

You will have to use phrase:

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

So now it sorts:

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

The only thing you would have to change is to take the last element instead of the first, probably in the second clause of quicksort//1, like this:

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

This use of append/3 leaves behind a choice point; you could write your own list_front_last/3 if you want, or use

once( append(...) )

Hope that helps.

EDIT:

you can change your implementation of lastElement just a bit:

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

You have already unpacked the first value in the head of quicksort//1:

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

so you can directly use

list_front_last(Xs, X, Front, Pivot)

instead of the call to append/3.

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

1 Answers