/* 

  qsort benchmark in Picat.

  Prolog code from 
  http://www.jekejeke.ch/idatab/doclet/prod/en/docs/05_run/15_stdy/06_bench/09_programs/05_qsort/01_qsort.p.html

  This Picat model was created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/


% import util.
% import cp.


main => go.



/**
 * Prolog code for the quick sort benchmark.
 *
 * This is the benchmark of page 220 of:
 * Warren, D.H.D. (1983): Applied Logic – Its Use and
 * Implementation as a Programming Tool,
 * Technical Note 290, SRI International, 1983
 *
 * Copyright 2010, XLOG Technologies GmbH, Switzerland
 * Jekejeke Prolog 0.8.3 (a fast and small prolog interpreter)
 */

partition([],_,L1,L2) => L1 = [], L2=[].
partition([X|L],Y,LL,L2), X =< Y =>
      LL=[X|L1],
      partition(L,Y,L1,L2).
partition([X|L],Y,L1,LL) =>
      LL = [X|L2],
      partition(L,Y,L1,L2).

qsort([], R1, R2) => R1 = R2 .
qsort([X|L], R0, R) =>
      partition(L, X, L1, L2),
      qsort(L2, R0, R1),
      qsort(L1, [X|R1], R).

index(-)
dataqsort([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]).

go =>
    dataqsort(X),
    qsort(X,[],Y),
    writeln(Y).


go2 =>
    dataqsort(X),
    qsort(X,[],_Y).