Mercurial > hg > Applications > Tokio
comparison Examples/sorter/sort3 @ 0:cfb7c6b24319
Initial revision
author | kono |
---|---|
date | Thu, 30 Aug 2007 14:57:44 +0900 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:cfb7c6b24319 |
---|---|
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 |