home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 4 / DATAFILE_PDCD4.iso / unix / unixlib36d / src / c / qsort < prev    next >
Text File  |  1994-03-08  |  4KB  |  216 lines
  1. #ifdef __STDC__
  2. static char sccs_id[] = "@(#) qsort.c 2.3 " __DATE__ " HJR";
  3. #else
  4. static char sccs_id[] = "@(#) qsort.c 2.3 26/9/90 HJR";
  5. #endif
  6.  
  7. /* qsort.c (c) Copyright 1990 H.Rogers */
  8.  
  9. #ifdef __STDC__
  10. #include <stddef.h>
  11. #include <stdlib.h>
  12. #else
  13. #include "sys/types.h"
  14. extern void qsort ();
  15. #endif
  16. #include <string.h>
  17.  
  18. #define N_INSERT    8
  19.  
  20. static char *__t;
  21.  
  22. static size_t __z;
  23. #ifdef __STDC__
  24. static int (*__c) (const void *, const void *);
  25. #else
  26. static int (*__c) ();
  27. #endif
  28.  
  29. /* fast insertion sort - used for n <= N_INSERT */
  30.  
  31. #ifdef __STDC__
  32. static void
  33. __isort (register char *b, register size_t n)
  34. #else
  35. static void
  36. __isort (b, n)
  37.      register char *b;
  38.      register size_t n;
  39. #endif
  40. {
  41.   register size_t z = __z;
  42. #ifdef __STDC__
  43.   register int (*c) (const void *, const void *) = __c;
  44. #else
  45.   register int (*c) () = __c;
  46. #endif
  47.   register char *m, *e, *p;
  48.   register char *t;
  49.  
  50. #define swap(x,y) (memcpy(t,x,z),memcpy(x,y,z),memcpy(y,t,z))
  51. #define move(x,y,z) memmove(x,y,z)
  52. #define push(x) memcpy(t,x,z)
  53. #define pull(x) memcpy(x,t,z)
  54.  
  55.   t = __t;
  56.  
  57.   e = b + (n * z);        /* past end */
  58.  
  59. /* find minimum */
  60.  
  61.   for (m = p = b; (p += z) < e;)
  62.     if ((*c) (m, p) > 0)
  63.       m = p;
  64.  
  65. /* swap minimum into base */
  66.  
  67.   if (m != b)
  68.     swap (m, b);
  69.  
  70. /* standard insertion sort */
  71.  
  72.   for (m = b; (p = m += z) < e;)
  73.     {
  74.       while ((*c) (p -= z, m) > 0);
  75.       if ((p += z) != m)
  76.     push (m), move (p + z, p, m - p), pull (p);
  77.     }
  78.  
  79. #undef swap
  80. #undef move
  81. #undef push
  82. #undef pull
  83. }
  84.  
  85. /* quicksort - used for n > N_INSERT */
  86.  
  87. #ifdef __STDC__
  88. static void
  89. __qsort (register char *b, register size_t n)
  90. #else
  91. static void
  92. __qsort (b, n)
  93.      register char *b;
  94.      register size_t n;
  95. #endif
  96. {
  97.   register size_t z = __z;
  98. #ifdef __STDC__
  99.   register int (*c) (const void *, const void *) = __c;
  100. #else
  101.   register int (*c) () = __c;
  102. #endif
  103.   register char *m, *e, *p, *t;
  104.   register int i, j, k;
  105.  
  106. #define swap(x,y) (memcpy(t,x,z),memcpy(x,y,z),memcpy(y,t,z))
  107.  
  108. loop:
  109.  
  110.   t = __t;
  111.  
  112.   m = b + ((n >> 1) * z);    /* middle */
  113.   e = b + ((n - 1) * z);    /* end */
  114.  
  115. /* find pivot - median of b,m,e */
  116.  
  117.   if ((*c) (b, m) >= 0)
  118.     p = b;
  119.   else
  120.     p = m, m = b;
  121.   if ((*c) (p, e) > 0)
  122.     p = ((*c) (m, e) >= 0) ? m : e;
  123.  
  124. /* swap pivot into base */
  125.  
  126.   if (p != b)
  127.     swap (p, b);
  128.  
  129. /* standard quicksort & check for flat partition */
  130.  
  131.   m = b;
  132.   i = 0;
  133.   j = 1;
  134.   for (p = b; (p += z) <= e;)
  135.     {
  136.       if (!(k = (*c) (p, b)))
  137.     j++;
  138.       if (k < 0)
  139.     {
  140.       if ((m += z) != p)
  141.         swap (m, p);
  142.       i++;
  143.     }
  144.     }
  145.  
  146.   if (j == n)
  147.     return;            /* exit if flat */
  148.  
  149.   if (b != m)
  150.     swap (b, m);
  151.  
  152.   m += z;
  153.  
  154. /* sort smallest partition first */
  155.  
  156.   if (i < (n >> 1))
  157.     {
  158.       if (i > N_INSERT)
  159.     __qsort (b, i);
  160.       else if (i > 1)
  161.     __isort (b, i);
  162.       i = n - i - 1;
  163.     }
  164.   else
  165.     {
  166.       i = n - i - 1;
  167.       if (i > N_INSERT)
  168.     __qsort (m, i);
  169.       else if (i > 1)
  170.     __isort (m, i);
  171.       i = n - i - 1;
  172.       m = b;
  173.     }
  174.  
  175.   if (i > N_INSERT)
  176.     {
  177.       b = m;
  178.       n = i;
  179.       goto loop;
  180.     }                /* iterate larger partition */
  181.   else if (i > 1)
  182.     __isort (m, i);
  183.  
  184. #undef swap
  185. }
  186.  
  187. #ifdef __STDC__
  188. void
  189. qsort (register void *v, register size_t n, register size_t z,
  190.        register int (*c) (const void *, const void *))
  191. #else
  192. void
  193. qsort (v, n, z, c)
  194.      register void *v;
  195.      register size_t n;
  196.      register size_t z;
  197.      register int (*c) ();
  198. #endif
  199. {
  200.   if (n < 2)
  201.     return;
  202.  
  203.   if (!(__t = malloc (z)))
  204.     return;
  205.  
  206.   __z = z;
  207.   __c = c;
  208.  
  209.   if (n > N_INSERT)
  210.     __qsort ((char *) v, n);
  211.   else if (n > 1)
  212.     __isort ((char *) v, n);
  213.  
  214.   free (__t);
  215. }
  216.