1 | /*************************************************************************/ |
---|
2 | /* */ |
---|
3 | /* Sorting utilities */ |
---|
4 | /* ----------------- */ |
---|
5 | /* */ |
---|
6 | /*************************************************************************/ |
---|
7 | |
---|
8 | |
---|
9 | #include "defns.i" |
---|
10 | #include "types.i" |
---|
11 | #include "extern.i" |
---|
12 | |
---|
13 | |
---|
14 | |
---|
15 | /*************************************************************************/ |
---|
16 | /* */ |
---|
17 | /* Sort items from Fp to Lp on attribute a */ |
---|
18 | /* */ |
---|
19 | /*************************************************************************/ |
---|
20 | |
---|
21 | |
---|
22 | Quicksort(Fp, Lp, Att, Exchange) |
---|
23 | /* --------- */ |
---|
24 | ItemNo Fp, Lp; |
---|
25 | Attribute Att; |
---|
26 | void (*Exchange)(); |
---|
27 | { |
---|
28 | register ItemNo Lower, Middle; |
---|
29 | register float Thresh; |
---|
30 | register ItemNo i; |
---|
31 | |
---|
32 | if ( Fp < Lp ) |
---|
33 | { |
---|
34 | Thresh = CVal(Item[Lp], Att); |
---|
35 | |
---|
36 | /* Isolate all items with values <= threshold */ |
---|
37 | |
---|
38 | Middle = Fp; |
---|
39 | |
---|
40 | for ( i = Fp ; i < Lp ; i++ ) |
---|
41 | { |
---|
42 | if ( CVal(Item[i], Att) <= Thresh ) |
---|
43 | { |
---|
44 | if ( i != Middle ) (*Exchange)(Middle, i); |
---|
45 | Middle++; |
---|
46 | } |
---|
47 | } |
---|
48 | |
---|
49 | /* Extract all values equal to the threshold */ |
---|
50 | |
---|
51 | Lower = Middle - 1; |
---|
52 | |
---|
53 | for ( i = Lower ; i >= Fp ; i-- ) |
---|
54 | { |
---|
55 | if ( CVal(Item[i], Att) == Thresh ) |
---|
56 | { |
---|
57 | if ( i != Lower ) (*Exchange)(Lower, i); |
---|
58 | Lower--; |
---|
59 | } |
---|
60 | } |
---|
61 | |
---|
62 | /* Sort the lower values */ |
---|
63 | |
---|
64 | Quicksort(Fp, Lower, Att, Exchange); |
---|
65 | |
---|
66 | /* Position the middle element */ |
---|
67 | |
---|
68 | (*Exchange)(Middle, Lp); |
---|
69 | |
---|
70 | /* Sort the higher values */ |
---|
71 | |
---|
72 | Quicksort(Middle+1, Lp, Att, Exchange); |
---|
73 | } |
---|
74 | } |
---|