Quicksort in Prolog
quicksort divides the list by choosing (arbitrary) the first element,
called a pivot, and using this element to split the list into Left and
Right. Left has all elements smaller than the pivot. Right
has all elements larger than the pivot. The sorted list is [Left,
pivot, Right].
quicksort([X|Xs],Ys) :-
partition(Xs,X,Left,Right),
quicksort(Left,Ls),
quicksort(Right,Rs),
append(Ls,[X|Rs],Ys).
quicksort([],[]).
partition([X|Xs],Y,[X|Ls],Rs) :-
X <= Y,
partition(Xs,Y,Ls,Rs).
partition([X|Xs],Y,Ls,[X|Rs]) :-
X > Y,
partition(Xs,Y,Ls,Rs).
partition([],Y,[],[]).
append([],Ys,Ys).
append([X|Xs],Ys,[X|Zs]) :-
append(Xs,Ys,Zs).
Explanation
quicksort(Xs,Ys) sorts list Xs into ascending order list Ys. (or
Ys is an ordered permutation of Xs).
Ys is a sorted [X|Xs] where Left and Right is a result of partitioning
Xs by X, Ls and Rs are the sorted Left and Right recursively, and Ys is
the result of appending [X|Rs] to Ls.
partitioning [X|Xs] with Y gives list Ls (left) and Rs (right), if X is
less than or equal Y and partitioning Xs with Y gives Ls and Rs.
The base case is the empty list.
Wow, this is beautiful.