[26] | 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 | } |
---|