Prolog last element function returns whole list

Question

I have an assignment to implement quicksort in Prolog then return the final element. I have the quicksort working but when it gets to the last element call it returns the whole list. My last element works when run on its own but not when I call it at the end of quicksort. Any ideas as to what I need to change?

quicksort([],[]).
quicksort([H|T],Final) :- 
    partition(T,H,Left,Right), 
    quicksort(Left,Ls),                           
    quicksort(Right,Rs), 
    append(Ls,[H|Rs],Sorted), 
    lastelement(Final, [Sorted]).

partition([],Pivot,[],[]).
partition([H|T],Pivot,[H|Ls],Rs) :- H =< Pivot, partition(T,Pivot,Ls,Rs).
partition([H|T],Pivot,Ls,[H|Rs]) :- H > Pivot, partition(T,Pivot,Ls,Rs).

append([],Sorted,Sorted).
append([H|T],Sorted,[H|Z]) :- append(T,Sorted,Z).

lastelement(Final, [Final]).
lastelement(Final, [_|T]):- lastelement(Final,T).

Answer 1

As observed by @gusbro, it's not possible to define a recursive predicate whose base case produces a list and whose recursive step produces an element. Thus, a possible solution is:

quicksort([],[]).
quicksort([H|T], Sorted) :-
    mypartition(T, H, Left, Right),
    quicksort(Left,  Ls),
    quicksort(Right, Rs),
    myappend(Ls, [H|Rs], Sorted).

mypartition([], _Pivot,[],[]).
mypartition([H|T],Pivot,[H|Ls],Rs) :- H =< Pivot, mypartition(T,Pivot,Ls,Rs).
mypartition([H|T],Pivot,Ls,[H|Rs]) :- H > Pivot, mypartition(T,Pivot,Ls,Rs).

myappend([], Sorted, Sorted).
myappend([H|T], Sorted, [H|Z]) :- myappend(T, Sorted, Z).

lastelement(Final, [Final]).
lastelement(Final, [_|T]):- lastelement(Final,T).

quicksort_last(List, Last) :-
    quicksort(List, Sorted),
    lastelement(Last, Sorted).

Examples:

?- quicksort([61,46,59,27,12,38], S).
S = [12, 27, 38, 46, 59, 61] ;
false.

?- quicksort_last([61,46,59,27,12,38], S).
S = 61 ;
false.

A BETTER SOLUTION

The average complexity time of quicksort_last/2 is O(n lg n). Supposing that your solution must be basead on the idea of Quick Sort, a more efficient approach, with average complexity time O(n), is:

• To have a last item (aka, maximum item), the complete sorted list cannot be empty.
• After the partition:
  • If the right sublist is empty, then Pivot is the last element in the complete sorted list (because Pivot is bigger than all elements in the left sublist).
  • Otherwise, the last element in the right sublist is also the last element in the complete sorted list (because, if there is at least one item in the right sublist, then Pivot is smaller than it).

quick_last([Pivot|Rest], Last) :-
    mypartition(Rest, Pivot, _, Right),
    (   Right = []
    ->  Last = Pivot
    ;   quick_last(Right, Last) ).

Examples:

?- quick_last([61,46,59,27,12,38], S).
S = 61 ;
false.

?- quick_last([71, 100, 83, 97, 62, 6, 42, 3, 40], L).
L = 100 ;
false.

In the best case, at each recursive call of quick_last/2, the length of the list is divided by 2. Since the time consumed by partition/4 is proportional to the length of the list, we have T(n) = n + n/2 + n/4 + ... + 1 ≈ 2*n.

REMARK This solution is a particular case of an algorithm to find the k-th smallest element in an unordered list (see: quick-select).