====== Quicksort 2 ======
{{tag>sorting algorithms recursion}}
===== Description =====
Program implements quicksort algorithm.

**Source**:  PROLOG programming for artificial intelligence, 3rd Edition, Harlow, 2001, ISBN 0-201-40375-7.
===== Download =====
Program source code: {{quicksort_2.pl}}
===== Listing =====
<code prolog>
% Figure 9.3  A more efficient implementation of quicksort using difference-pair
% representation for lists. 


% quicksort( List, SortedList): sort List with the quicksort algorithm

quicksort( List, Sorted)  :-
  quicksort2( List, Sorted - [] ).

% quicksort2( List, SortedDiffList): sort List, result is represented as difference list

quicksort2( [], Z - Z).

quicksort2( [X | Tail], A1 - Z2)  :-
   split( X, Tail, Small, Big),
   quicksort2( Small, A1 - [X | A2] ),
   quicksort2( Big, A2 - Z2).

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).</code>
===== Comments =====