Program implements quicksort algorithm.

Source: PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.

Program source code: quicksort.pl

% Figure 9.2  Quicksort.
 
 
% quicksort( List, SortedList): sort List by the quicksort algorithm
 
quicksort( [], []).
 
quicksort( [X|Tail], Sorted)  :-
   split( X, Tail, Small, Big),
   quicksort( Small, SortedSmall),
   quicksort( Big, SortedBig),
   conc( SortedSmall, [X|SortedBig], Sorted).
 
split( X, [], [], []).
 
split( X, [Y|Tail], [Y|Small], Big)  :-
   gt( X, Y), !,
   split( X, Tail, Small, Big).
 
split( X, [Y|Tail], Small, [Y|Big])  :-
   split( X, Tail, Small, Big).
 
gt(A,B):-A > B.
 
%  conc(L1,L2,L3): list L3 is th econcatenation of lists L1 and L2
 
conc( [], L, L).
 
conc( [X | L1], L2, [X | L3])  :-
  conc( L1, L2, L3).