daily pastebin goal
74%
SHARE
TWEET

Untitled

a guest Sep 4th, 2010 69 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /***
  2. *qsort.c - quicksort algorithm; qsort() library function for sorting arrays
  3. *
  4. *       Copyright (c) 1985-1997, Microsoft Corporation. All rights reserved.
  5. *
  6. *Purpose:
  7. *       To implement the qsort() routine for sorting arrays.
  8. *
  9. *******************************************************************************/
  10.  
  11. #include <cruntime.h>
  12. #include <stdlib.h>
  13. #include <search.h>
  14.  
  15. /* prototypes for local routines */
  16. static void __cdecl shortsort(char *lo, char *hi, unsigned width,
  17.                 int (__cdecl *comp)(const void *, const void *));
  18. static void __cdecl swap(char *p, char *q, unsigned int width);
  19.  
  20. /* this parameter defines the cutoff between using quick sort and
  21.    insertion sort for arrays; arrays with lengths shorter or equal to the
  22.    below value use insertion sort */
  23.  
  24. #define CUTOFF 8            /* testing shows that this is good value */
  25.  
  26.  
  27. /***
  28. *qsort(base, num, wid, comp) - quicksort function for sorting arrays
  29. *
  30. *Purpose:
  31. *       quicksort the array of elements
  32. *       side effects:  sorts in place
  33. *
  34. *Entry:
  35. *       char *base = pointer to base of array
  36. *       unsigned num  = number of elements in the array
  37. *       unsigned width = width in bytes of each array element
  38. *       int (*comp)() = pointer to function returning analog of strcmp for
  39. *               strings, but supplied by user for comparing the array elements.
  40. *               it accepts 2 pointers to elements and returns neg if 1<2, 0 if
  41. *               1=2, pos if 1>2.
  42. *
  43. *Exit:
  44. *       returns void
  45. *
  46. *Exceptions:
  47. *
  48. *******************************************************************************/
  49.  
  50. /* sort the array between lo and hi (inclusive) */
  51.  
  52. void __cdecl qsort (
  53.     void *base,
  54.     unsigned num,
  55.     unsigned width,
  56.     int (__cdecl *comp)(const void *, const void *)
  57.     )
  58. {
  59.     char *lo, *hi;              /* ends of sub-array currently sorting */
  60.     char *mid;                  /* points to middle of subarray */
  61.     char *loguy, *higuy;        /* traveling pointers for partition step */
  62.     unsigned size;              /* size of the sub-array */
  63.     char *lostk[30], *histk[30];
  64.     int stkptr;                 /* stack for saving sub-array to be processed */
  65.  
  66.     /* Note: the number of stack entries required is no more than
  67.        1 + log2(size), so 30 is sufficient for any array */
  68.  
  69.     if (num < 2 || width == 0)
  70.         return;                 /* nothing to do */
  71.  
  72.     stkptr = 0;                 /* initialize stack */
  73.  
  74.     lo = base;
  75.     hi = (char *)base + width * (num-1);        /* initialize limits */
  76.  
  77.     /* this entry point is for pseudo-recursion calling: setting
  78.        lo and hi and jumping to here is like recursion, but stkptr is
  79.        prserved, locals aren't, so we preserve stuff on the stack */
  80. recurse:
  81.  
  82.     size = (hi - lo) / width + 1;        /* number of el's to sort */
  83.  
  84.     /* below a certain size, it is faster to use a O(n^2) sorting method */
  85.     if (size <= CUTOFF) {
  86.          shortsort(lo, hi, width, comp);
  87.     }
  88.     else {
  89.         /* First we pick a partititioning element.  The efficiency of the
  90.            algorithm demands that we find one that is approximately the
  91.            median of the values, but also that we select one fast.  Using
  92.            the first one produces bad performace if the array is already
  93.            sorted, so we use the middle one, which would require a very
  94.            wierdly arranged array for worst case performance.  Testing shows
  95.            that a median-of-three algorithm does not, in general, increase
  96.            performance. */
  97.  
  98.         mid = lo + (size / 2) * width;      /* find middle element */
  99.         swap(mid, lo, width);               /* swap it to beginning of array */
  100.  
  101.         /* We now wish to partition the array into three pieces, one
  102.            consisiting of elements <= partition element, one of elements
  103.            equal to the parition element, and one of element >= to it.  This
  104.            is done below; comments indicate conditions established at every
  105.            step. */
  106.  
  107.         loguy = lo;
  108.         higuy = hi + width;
  109.  
  110.         /* Note that higuy decreases and loguy increases on every iteration,
  111.            so loop must terminate. */
  112.         for (;;) {
  113.             /* lo <= loguy < hi, lo < higuy <= hi + 1,
  114.                A[i] <= A[lo] for lo <= i <= loguy,
  115.                A[i] >= A[lo] for higuy <= i <= hi */
  116.  
  117.             do  {
  118.                 loguy += width;
  119.             } while (loguy <= hi && comp(loguy, lo) <= 0);
  120.  
  121.             /* lo < loguy <= hi+1, A[i] <= A[lo] for lo <= i < loguy,
  122.                either loguy > hi or A[loguy] > A[lo] */
  123.  
  124.             do  {
  125.                 higuy -= width;
  126.             } while (higuy > lo && comp(higuy, lo) >= 0);
  127.  
  128.             /* lo-1 <= higuy <= hi, A[i] >= A[lo] for higuy < i <= hi,
  129.                either higuy <= lo or A[higuy] < A[lo] */
  130.  
  131.             if (higuy < loguy)
  132.                 break;
  133.  
  134.             /* if loguy > hi or higuy <= lo, then we would have exited, so
  135.                A[loguy] > A[lo], A[higuy] < A[lo],
  136.                loguy < hi, highy > lo */
  137.  
  138.             swap(loguy, higuy, width);
  139.  
  140.             /* A[loguy] < A[lo], A[higuy] > A[lo]; so condition at top
  141.                of loop is re-established */
  142.         }
  143.  
  144.         /*     A[i] >= A[lo] for higuy < i <= hi,
  145.                A[i] <= A[lo] for lo <= i < loguy,
  146.                higuy < loguy, lo <= higuy <= hi
  147.            implying:
  148.                A[i] >= A[lo] for loguy <= i <= hi,
  149.                A[i] <= A[lo] for lo <= i <= higuy,
  150.                A[i] = A[lo] for higuy < i < loguy */
  151.  
  152.         swap(lo, higuy, width);     /* put partition element in place */
  153.  
  154.         /* OK, now we have the following:
  155.               A[i] >= A[higuy] for loguy <= i <= hi,
  156.               A[i] <= A[higuy] for lo <= i < higuy
  157.               A[i] = A[lo] for higuy <= i < loguy    */
  158.  
  159.         /* We've finished the partition, now we want to sort the subarrays
  160.            [lo, higuy-1] and [loguy, hi].
  161.            We do the smaller one first to minimize stack usage.
  162.            We only sort arrays of length 2 or more.*/
  163.  
  164.         if ( higuy - 1 - lo >= hi - loguy ) {
  165.             if (lo + width < higuy) {
  166.                 lostk[stkptr] = lo;
  167.                 histk[stkptr] = higuy - width;
  168.                 ++stkptr;
  169.             }                           /* save big recursion for later */
  170.  
  171.             if (loguy < hi) {
  172.                 lo = loguy;
  173.                 goto recurse;           /* do small recursion */
  174.             }
  175.         }
  176.         else {
  177.             if (loguy < hi) {
  178.                 lostk[stkptr] = loguy;
  179.                 histk[stkptr] = hi;
  180.                 ++stkptr;               /* save big recursion for later */
  181.             }
  182.  
  183.             if (lo + width < higuy) {
  184.                 hi = higuy - width;
  185.                 goto recurse;           /* do small recursion */
  186.             }
  187.         }
  188.     }
  189.  
  190.     /* We have sorted the array, except for any pending sorts on the stack.
  191.        Check if there are any, and do them. */
  192.  
  193.     --stkptr;
  194.     if (stkptr >= 0) {
  195.         lo = lostk[stkptr];
  196.         hi = histk[stkptr];
  197.         goto recurse;           /* pop subarray from stack */
  198.     }
  199.     else
  200.         return;                 /* all subarrays done */
  201. }
  202.  
  203.  
  204. /***
  205. *shortsort(hi, lo, width, comp) - insertion sort for sorting short arrays
  206. *
  207. *Purpose:
  208. *       sorts the sub-array of elements between lo and hi (inclusive)
  209. *       side effects:  sorts in place
  210. *       assumes that lo < hi
  211. *
  212. *Entry:
  213. *       char *lo = pointer to low element to sort
  214. *       char *hi = pointer to high element to sort
  215. *       unsigned width = width in bytes of each array element
  216. *       int (*comp)() = pointer to function returning analog of strcmp for
  217. *               strings, but supplied by user for comparing the array elements.
  218. *               it accepts 2 pointers to elements and returns neg if 1<2, 0 if
  219. *               1=2, pos if 1>2.
  220. *
  221. *Exit:
  222. *       returns void
  223. *
  224. *Exceptions:
  225. *
  226. *******************************************************************************/
  227.  
  228. static void __cdecl shortsort (
  229.     char *lo,
  230.     char *hi,
  231.     unsigned width,
  232.     int (__cdecl *comp)(const void *, const void *)
  233.     )
  234. {
  235.     char *p, *max;
  236.  
  237.     /* Note: in assertions below, i and j are alway inside original bound of
  238.        array to sort. */
  239.  
  240.     while (hi > lo) {
  241.         /* A[i] <= A[j] for i <= j, j > hi */
  242.         max = lo;
  243.         for (p = lo+width; p <= hi; p += width) {
  244.             /* A[i] <= A[max] for lo <= i < p */
  245.             if (comp(p, max) > 0) {
  246.                 max = p;
  247.             }
  248.             /* A[i] <= A[max] for lo <= i <= p */
  249.         }
  250.  
  251.         /* A[i] <= A[max] for lo <= i <= hi */
  252.  
  253.         swap(max, hi, width);
  254.  
  255.         /* A[i] <= A[hi] for i <= hi, so A[i] <= A[j] for i <= j, j >= hi */
  256.  
  257.         hi -= width;
  258.  
  259.         /* A[i] <= A[j] for i <= j, j > hi, loop top condition established */
  260.     }
  261.     /* A[i] <= A[j] for i <= j, j > lo, which implies A[i] <= A[j] for i < j,
  262.        so array is sorted */
  263. }
  264.  
  265.  
  266. /***
  267. *swap(a, b, width) - swap two elements
  268. *
  269. *Purpose:
  270. *       swaps the two array elements of size width
  271. *
  272. *Entry:
  273. *       char *a, *b = pointer to two elements to swap
  274. *       unsigned width = width in bytes of each array element
  275. *
  276. *Exit:
  277. *       returns void
  278. *
  279. *Exceptions:
  280. *
  281. *******************************************************************************/
  282.  
  283. static void __cdecl swap (
  284.     char *a,
  285.     char *b,
  286.     unsigned width
  287.     )
  288. {
  289.     char tmp;
  290.  
  291.     if ( a != b )
  292.         /* Do the swap one character at a time to avoid potential alignment
  293.            problems. */
  294.         while ( width-- ) {
  295.             tmp = *a;
  296.             *a++ = *b;
  297.             *b++ = tmp;
  298.         }
  299. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top