lib/ansi/qsort.c

   1 /*
   2  * (c) copyright 1987 by the Vrije Universiteit, Amsterdam, The Netherlands.
   3  * See the copyright notice in the ACK home directory, in the file "Copyright".
   4  */
   5 /* $Header$ */
   6
   7 #include        <stdlib.h>
   8
   9 static  void qsort1(char *, char *, size_t);
  10 static  int (*qcompar)(const char *, const char *);
  11 static  void qexchange(char *, char *, size_t);
  12 static  void q3exchange(char *, char *, char *, size_t);
  13
  14 void
  15 qsort(void *base, size_t nel, size_t width,
  16       int (*compar)(const void *, const void *))
  17 {
  18         /* when nel is 0, the expression '(nel - 1) * width' is wrong */
  19         if (!nel) return;
  20         qcompar = (int (*)(const char *, const char *)) compar;
  21         qsort1(base, (char *)base + (nel - 1) * width, width);
  22 }
  23
  24 static void
  25 qsort1(char *a1, char *a2, register size_t width)
  26 {
  27         register char *left, *right;
  28         register char *lefteq, *righteq;
  29         int cmp;
  30
  31         for (;;) {
  32                 if (a2 <= a1) return;
  33                 left = a1;
  34                 right = a2;
  35                 lefteq = righteq = a1 + width * (((a2-a1)+width)/(2*width));
  36                 /*
  37                    Pick an element in the middle of the array.
  38                    We will collect the equals around it.
  39                    "lefteq" and "righteq" indicate the left and right
  40                    bounds of the equals respectively.
  41                    Smaller elements end up left of it, larger elements end
  42                    up right of it.
  43                 */
  44 again:
  45                 while (left < lefteq && (cmp = (*qcompar)(left, lefteq)) <= 0) {
  46                         if (cmp < 0) {
  47                                 /* leave it where it is */
  48                                 left += width;
  49                         }
  50                         else {
  51                                 /* equal, so exchange with the element to
  52                                    the left of the "equal"-interval.
  53                                 */
  54                                 lefteq -= width;
  55                                 qexchange(left, lefteq, width);
  56                         }
  57                 }
  58                 while (right > righteq) {
  59                         if ((cmp = (*qcompar)(right, righteq)) < 0) {
  60                                 /* smaller, should go to left part
  61                                 */
  62                                 if (left < lefteq) {
  63                                         /* yes, we had a larger one at the
  64                                            left, so we can just exchange
  65                                         */
  66                                         qexchange(left, right, width);
  67                                         left += width;
  68                                         right -= width;
  69                                         goto again;
  70                                 }
  71                                 /* no more room at the left part, so we
  72                                    move the "equal-interval" one place to the
  73                                    right, and the smaller element to the
  74                                    left of it.
  75                                    This is best expressed as a three-way
  76                                    exchange.
  77                                 */
  78                                 righteq += width;
  79                                 q3exchange(left, righteq, right, width);
  80                                 lefteq += width;
  81                                 left = lefteq;
  82                         }
  83                         else if (cmp == 0) {
  84                                 /* equal, so exchange with the element to
  85                                    the right of the "equal-interval"
  86                                 */
  87                                 righteq += width;
  88                                 qexchange(right, righteq, width);
  89                         }
  90                         else    /* just leave it */ right -= width;
  91                 }
  92                 if (left < lefteq) {
  93                         /* larger element to the left, but no more room,
  94                            so move the "equal-interval" one place to the
  95                            left, and the larger element to the right
  96                            of it.
  97                         */
  98                         lefteq -= width;
  99                         q3exchange(right, lefteq, left, width);
 100                         righteq -= width;
 101                         right = righteq;
 102                         goto again;
 103                 }
 104                 /* now sort the "smaller" part */
 105                 qsort1(a1, lefteq - width, width);
 106                 /* and now the larger, saving a subroutine call
 107                    because of the for(;;)
 108                 */
 109                 a1 = righteq + width;
 110         }
 111         /*NOTREACHED*/
 112 }
 113
 114 static void
 115 qexchange(register char *p, register char *q,
 116           register size_t n)
 117 {
 118         register int c;
 119
 120         while (n-- > 0) {
 121                 c = *p;
 122                 *p++ = *q;
 123                 *q++ = c;
 124         }
 125 }
 126
 127 static void
 128 q3exchange(register char *p, register char *q, register char *r,
 129            register size_t n)
 130 {
 131         register int c;
 132
 133         while (n-- > 0) {
 134                 c = *p;
 135                 *p++ = *r;
 136                 *r++ = *q;
 137                 *q++ = c;
 138         }
 139 }