Go to most recent revision | Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 1805 | yogev_ezra | 1 | static void shortsort(char *lo, char *hi, unsigned width, |
| 2 | int (*comp)(const void *, const void *)); |
||
| 3 | |||
| 4 | static void swap(char *p, char *q, unsigned width); |
||
| 5 | |||
| 6 | /* this parameter defines the cutoff between using quick sort and |
||
| 7 | insertion sort for arrays; arrays with lengths shorter or equal to the |
||
| 8 | below value use insertion sort */ |
||
| 9 | |||
| 10 | #define CUTOFF 8 /* testing shows that this is good value */ |
||
| 11 | |||
| 12 | #define STKSIZ (8*sizeof(void*) - 2) |
||
| 13 | |||
| 14 | /*** |
||
| 15 | *qsort(base, num, wid, comp) - quicksort function for sorting arrays |
||
| 16 | * |
||
| 17 | *Purpose: |
||
| 18 | * quicksort the array of elements |
||
| 19 | * side effects: sorts in place |
||
| 20 | * maximum array size is number of elements times size of elements, |
||
| 21 | * but is limited by the virtual address space of the processor |
||
| 22 | * |
||
| 23 | *Entry: |
||
| 24 | * char *base = pointer to base of array |
||
| 25 | * unsigned num = number of elements in the array |
||
| 26 | * unsigned width = width in bytes of each array element |
||
| 27 | * int (*comp)() = pointer to function returning analog of strcmp for |
||
| 28 | * strings, but supplied by user for comparing the array elements. |
||
| 29 | * it accepts 2 pointers to elements. |
||
| 30 | * Returns neg if 1<2, 0 if 1=2, pos if 1>2. |
||
| 31 | * |
||
| 32 | *Exit: |
||
| 33 | * returns void |
||
| 34 | * |
||
| 35 | *******************************************************************************/ |
||
| 36 | |||
| 37 | void qsort ( |
||
| 38 | void *base, |
||
| 39 | unsigned num, |
||
| 40 | unsigned width, |
||
| 41 | int (*comp)(const void *, const void *) |
||
| 42 | ) |
||
| 43 | { |
||
| 44 | /* Note: the number of stack entries required is no more than |
||
| 45 | 1 + log2(num), so 30 is sufficient for any array */ |
||
| 46 | char *lo, *hi; /* ends of sub-array currently sorting */ |
||
| 47 | char *mid; /* points to middle of subarray */ |
||
| 48 | char *loguy, *higuy; /* traveling pointers for partition step */ |
||
| 49 | unsigned size; /* size of the sub-array */ |
||
| 50 | char *lostk[STKSIZ], *histk[STKSIZ]; |
||
| 51 | int stkptr; /* stack for saving sub-array to be processed */ |
||
| 52 | |||
| 53 | if (num < 2) |
||
| 54 | return; /* nothing to do */ |
||
| 55 | |||
| 56 | stkptr = 0; /* initialize stack */ |
||
| 57 | |||
| 58 | lo = (char *)base; |
||
| 59 | hi = (char *)base + width * (num-1); /* initialize limits */ |
||
| 60 | |||
| 61 | /* this entry point is for pseudo-recursion calling: setting |
||
| 62 | lo and hi and jumping to here is like recursion, but stkptr is |
||
| 63 | preserved, locals aren't, so we preserve stuff on the stack */ |
||
| 64 | recurse: |
||
| 65 | |||
| 66 | size = (hi - lo) / width + 1; /* number of el's to sort */ |
||
| 67 | |||
| 68 | /* below a certain size, it is faster to use a O(n^2) sorting method */ |
||
| 69 | if (size <= CUTOFF) { |
||
| 70 | shortsort(lo, hi, width, comp); |
||
| 71 | } |
||
| 72 | else { |
||
| 73 | /* First we pick a partitioning element. The efficiency of the |
||
| 74 | algorithm demands that we find one that is approximately the median |
||
| 75 | of the values, but also that we select one fast. We choose the |
||
| 76 | median of the first, middle, and last elements, to avoid bad |
||
| 77 | performance in the face of already sorted data, or data that is made |
||
| 78 | up of multiple sorted runs appended together. Testing shows that a |
||
| 79 | median-of-three algorithm provides better performance than simply |
||
| 80 | picking the middle element for the latter case. */ |
||
| 81 | |||
| 82 | mid = lo + (size / 2) * width; /* find middle element */ |
||
| 83 | |||
| 84 | /* Sort the first, middle, last elements into order */ |
||
| 85 | if (comp(lo, mid) > 0) { |
||
| 86 | swap(lo, mid, width); |
||
| 87 | } |
||
| 88 | if (comp(lo, hi) > 0) { |
||
| 89 | swap(lo, hi, width); |
||
| 90 | } |
||
| 91 | if (comp(mid, hi) > 0) { |
||
| 92 | swap(mid, hi, width); |
||
| 93 | } |
||
| 94 | |||
| 95 | /* We now wish to partition the array into three pieces, one consisting |
||
| 96 | of elements <= partition element, one of elements equal to the |
||
| 97 | partition element, and one of elements > than it. This is done |
||
| 98 | below; comments indicate conditions established at every step. */ |
||
| 99 | |||
| 100 | loguy = lo; |
||
| 101 | higuy = hi; |
||
| 102 | |||
| 103 | /* Note that higuy decreases and loguy increases on every iteration, |
||
| 104 | so loop must terminate. */ |
||
| 105 | for (;;) { |
||
| 106 | /* lo <= loguy < hi, lo < higuy <= hi, |
||
| 107 | A[i] <= A[mid] for lo <= i <= loguy, |
||
| 108 | A[i] > A[mid] for higuy <= i < hi, |
||
| 109 | A[hi] >= A[mid] */ |
||
| 110 | |||
| 111 | /* The doubled loop is to avoid calling comp(mid,mid), since some |
||
| 112 | existing comparison funcs don't work when passed the same |
||
| 113 | value for both pointers. */ |
||
| 114 | |||
| 115 | if (mid > loguy) { |
||
| 116 | do { |
||
| 117 | loguy += width; |
||
| 118 | } while (loguy < mid && comp(loguy, mid) <= 0); |
||
| 119 | } |
||
| 120 | if (mid <= loguy) { |
||
| 121 | do { |
||
| 122 | loguy += width; |
||
| 123 | } while (loguy <= hi && comp(loguy, mid) <= 0); |
||
| 124 | } |
||
| 125 | |||
| 126 | /* lo < loguy <= hi+1, A[i] <= A[mid] for lo <= i < loguy, |
||
| 127 | either loguy > hi or A[loguy] > A[mid] */ |
||
| 128 | |||
| 129 | do { |
||
| 130 | higuy -= width; |
||
| 131 | } while (higuy > mid && comp(higuy, mid) > 0); |
||
| 132 | |||
| 133 | /* lo <= higuy < hi, A[i] > A[mid] for higuy < i < hi, |
||
| 134 | either higuy == lo or A[higuy] <= A[mid] */ |
||
| 135 | |||
| 136 | if (higuy < loguy) |
||
| 137 | break; |
||
| 138 | |||
| 139 | /* if loguy > hi or higuy == lo, then we would have exited, so |
||
| 140 | A[loguy] > A[mid], A[higuy] <= A[mid], |
||
| 141 | loguy <= hi, higuy > lo */ |
||
| 142 | |||
| 143 | swap(loguy, higuy, width); |
||
| 144 | |||
| 145 | /* If the partition element was moved, follow it. Only need |
||
| 146 | to check for mid == higuy, since before the swap, |
||
| 147 | A[loguy] > A[mid] implies loguy != mid. */ |
||
| 148 | |||
| 149 | if (mid == higuy) |
||
| 150 | mid = loguy; |
||
| 151 | |||
| 152 | /* A[loguy] <= A[mid], A[higuy] > A[mid]; so condition at top |
||
| 153 | of loop is re-established */ |
||
| 154 | } |
||
| 155 | |||
| 156 | /* A[i] <= A[mid] for lo <= i < loguy, |
||
| 157 | A[i] > A[mid] for higuy < i < hi, |
||
| 158 | A[hi] >= A[mid] |
||
| 159 | higuy < loguy |
||
| 160 | implying: |
||
| 161 | higuy == loguy-1 |
||
| 162 | or higuy == hi - 1, loguy == hi + 1, A[hi] == A[mid] */ |
||
| 163 | |||
| 164 | /* Find adjacent elements equal to the partition element. The |
||
| 165 | doubled loop is to avoid calling comp(mid,mid), since some |
||
| 166 | existing comparison funcs don't work when passed the same value |
||
| 167 | for both pointers. */ |
||
| 168 | |||
| 169 | higuy += width; |
||
| 170 | if (mid < higuy) { |
||
| 171 | do { |
||
| 172 | higuy -= width; |
||
| 173 | } while (higuy > mid && comp(higuy, mid) == 0); |
||
| 174 | } |
||
| 175 | if (mid >= higuy) { |
||
| 176 | do { |
||
| 177 | higuy -= width; |
||
| 178 | } while (higuy > lo && comp(higuy, mid) == 0); |
||
| 179 | } |
||
| 180 | |||
| 181 | /* OK, now we have the following: |
||
| 182 | higuy < loguy |
||
| 183 | lo <= higuy <= hi |
||
| 184 | A[i] <= A[mid] for lo <= i <= higuy |
||
| 185 | A[i] == A[mid] for higuy < i < loguy |
||
| 186 | A[i] > A[mid] for loguy <= i < hi |
||
| 187 | A[hi] >= A[mid] */ |
||
| 188 | |||
| 189 | /* We've finished the partition, now we want to sort the subarrays |
||
| 190 | [lo, higuy] and [loguy, hi]. |
||
| 191 | We do the smaller one first to minimize stack usage. |
||
| 192 | We only sort arrays of length 2 or more.*/ |
||
| 193 | |||
| 194 | if ( higuy - lo >= hi - loguy ) { |
||
| 195 | if (lo < higuy) { |
||
| 196 | lostk[stkptr] = lo; |
||
| 197 | histk[stkptr] = higuy; |
||
| 198 | ++stkptr; |
||
| 199 | } /* save big recursion for later */ |
||
| 200 | |||
| 201 | if (loguy < hi) { |
||
| 202 | lo = loguy; |
||
| 203 | goto recurse; /* do small recursion */ |
||
| 204 | } |
||
| 205 | } |
||
| 206 | else { |
||
| 207 | if (loguy < hi) { |
||
| 208 | lostk[stkptr] = loguy; |
||
| 209 | histk[stkptr] = hi; |
||
| 210 | ++stkptr; /* save big recursion for later */ |
||
| 211 | } |
||
| 212 | |||
| 213 | if (lo < higuy) { |
||
| 214 | hi = higuy; |
||
| 215 | goto recurse; /* do small recursion */ |
||
| 216 | } |
||
| 217 | } |
||
| 218 | } |
||
| 219 | |||
| 220 | /* We have sorted the array, except for any pending sorts on the stack. |
||
| 221 | Check if there are any, and do them. */ |
||
| 222 | |||
| 223 | --stkptr; |
||
| 224 | if (stkptr >= 0) { |
||
| 225 | lo = lostk[stkptr]; |
||
| 226 | hi = histk[stkptr]; |
||
| 227 | goto recurse; /* pop subarray from stack */ |
||
| 228 | } |
||
| 229 | else |
||
| 230 | return; /* all subarrays done */ |
||
| 231 | } |
||
| 232 | |||
| 233 | |||
| 234 | /*** |
||
| 235 | *shortsort(hi, lo, width, comp) - insertion sort for sorting short arrays |
||
| 236 | *shortsort_s(hi, lo, width, comp, context) - insertion sort for sorting short arrays |
||
| 237 | * |
||
| 238 | *Purpose: |
||
| 239 | * sorts the sub-array of elements between lo and hi (inclusive) |
||
| 240 | * side effects: sorts in place |
||
| 241 | * assumes that lo < hi |
||
| 242 | * |
||
| 243 | *Entry: |
||
| 244 | * char *lo = pointer to low element to sort |
||
| 245 | * char *hi = pointer to high element to sort |
||
| 246 | * unsigned width = width in bytes of each array element |
||
| 247 | * int (*comp)() = pointer to function returning analog of strcmp for |
||
| 248 | * strings, but supplied by user for comparing the array elements. |
||
| 249 | * it accepts 2 pointers to elements, together with a pointer to a context |
||
| 250 | * (if present). Returns neg if 1<2, 0 if 1=2, pos if 1>2. |
||
| 251 | * void *context - pointer to the context in which the function is |
||
| 252 | * called. This context is passed to the comparison function. |
||
| 253 | * |
||
| 254 | *Exit: |
||
| 255 | * returns void |
||
| 256 | * |
||
| 257 | *Exceptions: |
||
| 258 | * |
||
| 259 | *******************************************************************************/ |
||
| 260 | |||
| 261 | static void shortsort ( |
||
| 262 | char *lo, |
||
| 263 | char *hi, |
||
| 264 | unsigned width, |
||
| 265 | int (*comp)(const void *, const void *) |
||
| 266 | ) |
||
| 267 | { |
||
| 268 | char *p, *max; |
||
| 269 | |||
| 270 | /* Note: in assertions below, i and j are alway inside original bound of |
||
| 271 | array to sort. */ |
||
| 272 | |||
| 273 | while (hi > lo) { |
||
| 274 | /* A[i] <= A[j] for i <= j, j > hi */ |
||
| 275 | max = lo; |
||
| 276 | for (p = lo+width; p <= hi; p += width) { |
||
| 277 | /* A[i] <= A[max] for lo <= i < p */ |
||
| 278 | if (comp(p, max) > 0) { |
||
| 279 | max = p; |
||
| 280 | } |
||
| 281 | /* A[i] <= A[max] for lo <= i <= p */ |
||
| 282 | } |
||
| 283 | |||
| 284 | /* A[i] <= A[max] for lo <= i <= hi */ |
||
| 285 | |||
| 286 | swap(max, hi, width); |
||
| 287 | |||
| 288 | /* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */ |
||
| 289 | |||
| 290 | hi -= width; |
||
| 291 | |||
| 292 | /* A[i] <= A[j] for i <= j, j > hi, loop top condition established */ |
||
| 293 | } |
||
| 294 | /* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j, |
||
| 295 | so array is sorted */ |
||
| 296 | } |
||
| 297 | |||
| 298 | /*** |
||
| 299 | *swap(a, b, width) - swap two elements |
||
| 300 | * |
||
| 301 | *Purpose: |
||
| 302 | * swaps the two array elements of size width |
||
| 303 | * |
||
| 304 | *Entry: |
||
| 305 | * char *a, *b = pointer to two elements to swap |
||
| 306 | * unsigned width = width in bytes of each array element |
||
| 307 | * |
||
| 308 | *Exit: |
||
| 309 | * returns void |
||
| 310 | * |
||
| 311 | *Exceptions: |
||
| 312 | * |
||
| 313 | *******************************************************************************/ |
||
| 314 | |||
| 315 | static void swap ( |
||
| 316 | char *a, |
||
| 317 | char *b, |
||
| 318 | unsigned width |
||
| 319 | ) |
||
| 320 | { |
||
| 321 | char tmp; |
||
| 322 | |||
| 323 | if ( a != b ) |
||
| 324 | /* Do the swap one character at a time to avoid potential alignment |
||
| 325 | problems. */ |
||
| 326 | while ( width-- ) { |
||
| 327 | tmp = *a; |
||
| 328 | *a++ = *b; |
||
| 329 | *b++ = tmp; |
||
| 330 | } |
||
| 331 | } |