/* 

  Quicksort in Picat.

  From Rosetta code
  http://rosettacode.org/wiki/Sorting_algorithms/Quicksort

  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.


go =>
  _ = random2(),  
  S1 = [1,2,3,4,5,6,6,5,4,4,3,2,1],
  println(s1=qsort(S1)),

  S2 = [ random(0,100) : _I in 1..100],
  time(println(s2=qsort(S2))),

  S3 = [ random(0,10_000) : _I in 1..10_000],
  time(_T3 = qsort(S3)),

  println(shuffled),
  S4 = (1..10_000).shuffle(),
  time(_T4=qsort(S4)),

  nl.

% Prolog version
go2 =>
  _ = random2(),  
  S1 = [1,2,3,4,5,6,6,5,4,4,3,2,1],
  qsort(S1,T1),
  println(t1=T1),

  S2 = [ random(0,100) : _I in 1..100],
  time(qsort(S2,T2)),
  println(T2),

  S3 = [ random(0,10_000) : _I in 1..10_000],
  time(qsort(S3,_T3)),

  println(shuffled),
  S4 = (1..10_000).shuffle(),
  time(qsort(S4,_T4)),

  nl.


% Quicksort (as a function)
qsort([])    = [].
qsort([H|T]) = qsort([E : E in T, E =< H]) 
               ++ [H] ++
               qsort([E : E in T, E > H]).


% Shuffle a list
shuffle(List) = List2 => 
  List2 = List,
  Len = List.length,
  foreach(I in 1..Len) 
    R2 = random(1,Len),
    List2 := swap(List2,I,R2)
  end.


%
% Swap position I <=> J in list L
%
swap(L,I,J) = L2 =>
  L2 = L,
  T = L2[I],
  L2[I] := L2[J],
  L2[J] := T.


% {{trans|Prolog}}
qsort( [], [] ).
qsort( [H|U], S ) :-
  splitBy(H, U, L, R),
  qsort(L, SL),
  qsort(R, SR),
  append(SL, [H|SR], S).
 
% splitBy( H, U, LS, RS )
% True if LS = { L in U | L <= H }; RS = { R in U | R > H }
splitBy( _, [], [], []).
splitBy( H, [U|T], [U|LS], RS ) :- U =< H, splitBy(H, T, LS, RS).
splitBy( H, [U|T], LS, [U|RS] ) :- U  > H, splitBy(H, T, LS, RS).