blob: 683d1bc28c3b05480c0417f1461fe678659c2fe0 [file] [log] [blame]
:- dynamic seed/1.
/* VAX C-Prolog Benchmark Package */
/* Copyright 1985 by Tektronix, Inc., and Portland State University */
qsort(N) :-
generate(0,N,L), !,
quicksort(L,S).
generate(I,N,[]) :- I = N.
generate(I,N,L) :-
J is I+1,
random(1001,X),
generate(J,N,L1),
append([X],L1,L).
append([],L,L).
append([X|L1],L2,[X|L3]) :- append(L1,L2,L3).
seed(1301).
random(R,N) :- retract(seed(S)),
N is (S mod R)+1,
NewSeed is (125*S+1) mod 4096,
asserta(seed(NewSeed)), !.
quicksort([],[]).
quicksort([H|T],S) :- split(H,T,A,B),
quicksort(A,A1),
quicksort(B,B1),
append(A1,[H|B1],S).
split(H,[A|X],[A|Y],Z) :- A > H, split(H,X,Y,Z).
split(H,[A|X],Y,[A|Z]) :- A < H, split(H,X,Y,Z).
split(_,[],[],[]).