|
0
|
1 /* Program to do parallel quicksort. Ben Moszkowski
|
|
|
2 Initial version written around 29 Apr 84.
|
|
|
3 Subsequent changes made.
|
|
|
4 Updated 7 Feb 85.
|
|
|
5
|
|
|
6 translate to Tokio by S.Kono
|
|
|
7 Sun Aug 31 21:29:10 JST 1986
|
|
|
8 using functor and implicit sync
|
|
|
9 */
|
|
|
10
|
|
|
11 /* Support Routines */
|
|
|
12
|
|
|
13 '$function' (len(L) = Length :- functor(L,_,Length)).
|
|
|
14
|
|
|
15 '$function' (slice(List,From,To) = Slice
|
|
|
16 :- Size<--To-From+1,From=From1,To=To1,
|
|
|
17 (Size < 1, #(Slice = array) ;
|
|
|
18 #functor(Slice,array,Size),
|
|
|
19 slice(1,List,From1,To1,1,Slice))).
|
|
|
20
|
|
|
21 slice(N,List,From,To,_,_) :- N>To,!.
|
|
|
22 slice(N,List,From,To,I,Slice) :- N>=From,!,
|
|
|
23 NN = N+1,II = I+1,arg(N,List,E),arg(I,Slice,E),
|
|
|
24 slice(NN,List,From,To,II,Slice).
|
|
|
25 slice(N,List,From,To,I,Slice) :-
|
|
|
26 NN = N+1,
|
|
|
27 slice(NN,List,From,To,I,Slice).
|
|
|
28
|
|
|
29 '$function' (thof(I,L) = E :- arg(I,L,E)).
|
|
|
30
|
|
|
31 fixed_list(Array,Length) :- L <-- Length,
|
|
|
32 #functor(Array,array,L).
|
|
|
33
|
|
|
34 '$function' ( (if Cond then Yes else No) = Reply :-
|
|
|
35 if Cond then Yes=Reply else No=Reply).
|
|
|
36
|
|
|
37
|
|
|
38 /* Support Routines end */
|
|
|
39
|
|
|
40 par_quicksort(L) :-
|
|
|
41 if len(L) =< 1
|
|
|
42 then empty
|
|
|
43 else
|
|
|
44 stable(Pivot),
|
|
|
45 ( quick_partition(L,Pivot) &
|
|
|
46 sort_parts(L,Pivot) ).
|
|
|
47
|
|
|
48 quick_partition(L,Pivot) :-
|
|
|
49 I = 2, Z=1, J = len(L), J1=J+1,skip,
|
|
|
50 P = thof(1,L),
|
|
|
51 partition(I,J1,P,Z,J,L,Pivot).
|
|
|
52
|
|
|
53 partition(K,K,P,I,J,L,Pivot) :- !,@Pivot=I,@I=I,@thof(I,L)=P.
|
|
|
54 partition(K,E,P,I,J,L,Pivot) :- thof(K,L) < P,!, II=I+1,
|
|
|
55 @I=I, @thof(I,L) = thof(K,L), KK=K+1,
|
|
|
56 partition(KK,E,P,II,J,L,Pivot).
|
|
|
57 partition(K,E,P,I,J,L,Pivot) :- JJ=J-1,
|
|
|
58 @J=J, @thof(J,L) = thof(K,L), KK=K+1,
|
|
|
59 partition(KK,E,P,I,JJ,L,Pivot).
|
|
|
60
|
|
|
61 sort_parts(L,Pivot) :-
|
|
|
62 stable(thof(Pivot,L)),
|
|
|
63 quicksort_process(slice(L,1, Pivot-1)),
|
|
|
64 quicksort_process(slice(L,Pivot+1, len(L) )).
|
|
|
65 quicksort_process(L) :-
|
|
|
66 par_quicksort(L) & stable(L).
|
|
|
67
|
|
|
68 monitor(L) :-
|
|
|
69 fixed_list(Tag_list,len(L)),
|
|
|
70 #tag(1,len(L),L,Tag_list),
|
|
|
71 #((write('''List='''),write(L),put(" "),
|
|
|
72 write('''Tag_list='''),write(Tag_list))).
|
|
|
73
|
|
|
74 tag(I,J,_,_) :- I>J,!.
|
|
|
75 tag(I,K,L,T) :- (if I-1=thof(I,L) then 1 else 0) = thof(I,T),
|
|
|
76 J=I+1,tag(J,K,L,T).
|
|
|
77
|
|
|
78 /* test of quicksort */
|
|
|
79 sort_test(Init_vector) :-
|
|
|
80 %exists L :
|
|
|
81 stable(Init_vector),
|
|
|
82 fixed_list(L,len(Init_vector)),
|
|
|
83 L=Init_vector,
|
|
|
84 par_quicksort(L),
|
|
|
85 % #write(L).
|
|
|
86 monitor(L).
|
|
|
87
|
|
|
88 sort_test1 :- array(2,0,1)=List,sort_test(List).
|
|
|
89
|
|
|
90 sort_test2 :- array(2,4,9,1,0,10,6,8,7,5,3)=List,sort_test(List).
|
|
|
91
|
|
|
92 sort_test3 :- array(13,7,5,3,1,9,8,6,2,0,12,11,4,10)=List,sort_test(List).
|
|
|
93
|
