home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 5 / DATAFILE_PDCD5.iso / utilities / b / binprolog / !BinPro330 / progs / qsort < prev    next >
Encoding:
Text File  |  1994-09-10  |  1.1 KB  |  49 lines
  1. p:-[qsort].
  2.  
  3. go:-go('BMARK_qsort:').
  4.  
  5. go(Mes):-
  6.     write('use bp -h4000 -t1000 -s1000'),nl,
  7.     list(L),augment(L,L3),augment(L3,L9),augment(L9,L27),
  8.     statistics(global_stack,[H1,_]),
  9.     statistics(trail,[TR1,_]),
  10.     time(_),
  11.         qsort(L27,_Sorted,[]),
  12.     time(T),
  13.     statistics(global_stack,[H2,_]),H is H2-H1,
  14.     statistics(trail,[TR2,_]),TR is TR2-TR1,
  15.     write(Mes=[time(T),heap(H),trail(TR)]),nl.
  16.  
  17. go1:-L=[3,4,1,2,1,2,5,1,3,0,9,7],qsort(L,R,[]),write(L-R),nl.
  18.  
  19. on(X,[X|_]).
  20. on(X,[_|Xs]):-on(X,Xs).
  21.  
  22. augment(L,R):-findall(X,(on(Y,L),(X is Y+1;Y=X;X is Y-1)),R).
  23.  
  24. list([27,74,17,33,94,18,46,83,65, 2,
  25.         32,53,28,85,99,47,28,82, 6,11,
  26.         55,29,39,81,90,37,10, 0,66,51,
  27.          7,21,85,27,31,63,75, 4,95,99,
  28.         11,28,61,74,18,92,40,53,59, 8]).
  29.  
  30. qsort([],S,S).
  31. qsort([Y|L],S1,S3) :- partition(L,Y,S1,S3).
  32.  
  33. partition([],Y,[Y|S],S).
  34. partition([X|L],Y,S1,S3) :- 
  35.     partition1(L,Y,L1,L2,X),
  36.     qsort(L1,S1,[Y|S2]),
  37.     qsort(L2,S2,S3).
  38.  
  39. partition1(L,Y,[X|L1],L2,X) :-
  40.     X =< Y,!,
  41.     partition2(L,Y,L1,L2).
  42. partition1(L,Y,L1,[X|L2],X) :-
  43.     partition2(L,Y,L1,L2).
  44.  
  45. partition2([],_,[],[]).
  46. partition2([X|L],Y,L1,L2) :- partition1(L,Y,L1,L2,X).
  47.  
  48. time(T):-statistics(runtime,[_,T]).
  49.