% -*- Prolog -*-
%
% David H. D. Warren
%
% Quicksort a list of 50 integers
%
% $Id: 215,v 1.1 2000/11/12 12:22:46 peteg Exp $

:- compile(partition/4).
:- list(X) ::= [] ; [X | list(X)].

partition([X|L], Y, [X|L1], L2) :-
	X =< Y, !,
	partition(L, Y, L1, L2).
%partition(_A0, _B0, _C0, _D0) :-
%        unify(_A0, [_E0|_F0]),
%        unify(_C0, [_G0|_H0]),
%        unify(_E0, _G0),
%        le(_E0, _B0),
%        _cut,
%        partition(_F0, _B0, _H0, _D0).

partition([X|L], Y, L1, [X|L2]) :-
	partition(L, Y, L1, L2).
%partition(_A0, _B0, _C0, _D0) :-
%        unify(_A0, [_E0|_F0]),
%        unify(_D0, [_G0|_H0]),
%        unify(_E0, _G0),
%        partition(_F0, _B0, _C0, _H0).

partition([], _, [], []).

qsort_test :- 
	qsort([27, 74, 17, 33, 94, 18, 46, 83, 65, 2, 32, 53, 28, 85, 99,
	47, 28, 82, 6, 11, 55, 29, 39, 81, 90, 37, 10, 0, 66, 51, 7, 21, 85,
	27, 31,	63, 75, 4, 95, 99, 11, 28, 61, 74, 18, 92, 40, 53, 59, 8], X, []).

qsort([X|L], R, R0) :-
	partition(L, X, L1, L2),
	qsort(L2, R1, R0),
	qsort(L1, R, [X|R1]).
qsort([], R, R).

% Benchmarking
benchmark :-
	benchmark(200).

benchmark(0) :- !.
benchmark(X) :-
	qsort_test,
	X0 is X - 1,
	benchmark(X0).
