Back to index

glibc  2.9
qsort.c
Go to the documentation of this file.
00001 /* Copyright (C) 1991,1992,1996,1997,1999,2004 Free Software Foundation, Inc.
00002    This file is part of the GNU C Library.
00003    Written by Douglas C. Schmidt (schmidt@ics.uci.edu).
00004 
00005    The GNU C Library is free software; you can redistribute it and/or
00006    modify it under the terms of the GNU Lesser General Public
00007    License as published by the Free Software Foundation; either
00008    version 2.1 of the License, or (at your option) any later version.
00009 
00010    The GNU C Library is distributed in the hope that it will be useful,
00011    but WITHOUT ANY WARRANTY; without even the implied warranty of
00012    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013    Lesser General Public License for more details.
00014 
00015    You should have received a copy of the GNU Lesser General Public
00016    License along with the GNU C Library; if not, write to the Free
00017    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00018    02111-1307 USA.  */
00019 
00020 /* If you consider tuning this algorithm, you should consult first:
00021    Engineering a sort function; Jon Bentley and M. Douglas McIlroy;
00022    Software - Practice and Experience; Vol. 23 (11), 1249-1265, 1993.  */
00023 
00024 #include <alloca.h>
00025 #include <limits.h>
00026 #include <stdlib.h>
00027 #include <string.h>
00028 
00029 /* Byte-wise swap two items of size SIZE. */
00030 #define SWAP(a, b, size)                                             \
00031   do                                                                 \
00032     {                                                                \
00033       register size_t __size = (size);                                      \
00034       register char *__a = (a), *__b = (b);                                 \
00035       do                                                             \
00036        {                                                             \
00037          char __tmp = *__a;                                          \
00038          *__a++ = *__b;                                              \
00039          *__b++ = __tmp;                                             \
00040        } while (--__size > 0);                                              \
00041     } while (0)
00042 
00043 /* Discontinue quicksort algorithm when partition gets below this size.
00044    This particular magic number was chosen to work best on a Sun 4/260. */
00045 #define MAX_THRESH 4
00046 
00047 /* Stack node declarations used to store unfulfilled partition obligations. */
00048 typedef struct
00049   {
00050     char *lo;
00051     char *hi;
00052   } stack_node;
00053 
00054 /* The next 4 #defines implement a very fast in-line stack abstraction. */
00055 /* The stack needs log (total_elements) entries (we could even subtract
00056    log(MAX_THRESH)).  Since total_elements has type size_t, we get as
00057    upper bound for log (total_elements):
00058    bits per byte (CHAR_BIT) * sizeof(size_t).  */
00059 #define STACK_SIZE   (CHAR_BIT * sizeof(size_t))
00060 #define PUSH(low, high)     ((void) ((top->lo = (low)), (top->hi = (high)), ++top))
00061 #define       POP(low, high)       ((void) (--top, (low = top->lo), (high = top->hi)))
00062 #define       STACK_NOT_EMPTY      (stack < top)
00063 
00064 
00065 /* Order size using quicksort.  This implementation incorporates
00066    four optimizations discussed in Sedgewick:
00067 
00068    1. Non-recursive, using an explicit stack of pointer that store the
00069       next array partition to sort.  To save time, this maximum amount
00070       of space required to store an array of SIZE_MAX is allocated on the
00071       stack.  Assuming a 32-bit (64 bit) integer for size_t, this needs
00072       only 32 * sizeof(stack_node) == 256 bytes (for 64 bit: 1024 bytes).
00073       Pretty cheap, actually.
00074 
00075    2. Chose the pivot element using a median-of-three decision tree.
00076       This reduces the probability of selecting a bad pivot value and
00077       eliminates certain extraneous comparisons.
00078 
00079    3. Only quicksorts TOTAL_ELEMS / MAX_THRESH partitions, leaving
00080       insertion sort to order the MAX_THRESH items within each partition.
00081       This is a big win, since insertion sort is faster for small, mostly
00082       sorted array segments.
00083 
00084    4. The larger of the two sub-partitions is always pushed onto the
00085       stack first, with the algorithm then concentrating on the
00086       smaller partition.  This *guarantees* no more than log (total_elems)
00087       stack size is needed (actually O(1) in this case)!  */
00088 
00089 void
00090 _quicksort (void *const pbase, size_t total_elems, size_t size,
00091            __compar_d_fn_t cmp, void *arg)
00092 {
00093   register char *base_ptr = (char *) pbase;
00094 
00095   const size_t max_thresh = MAX_THRESH * size;
00096 
00097   if (total_elems == 0)
00098     /* Avoid lossage with unsigned arithmetic below.  */
00099     return;
00100 
00101   if (total_elems > MAX_THRESH)
00102     {
00103       char *lo = base_ptr;
00104       char *hi = &lo[size * (total_elems - 1)];
00105       stack_node stack[STACK_SIZE];
00106       stack_node *top = stack;
00107 
00108       PUSH (NULL, NULL);
00109 
00110       while (STACK_NOT_EMPTY)
00111         {
00112           char *left_ptr;
00113           char *right_ptr;
00114 
00115          /* Select median value from among LO, MID, and HI. Rearrange
00116             LO and HI so the three values are sorted. This lowers the
00117             probability of picking a pathological pivot value and
00118             skips a comparison for both the LEFT_PTR and RIGHT_PTR in
00119             the while loops. */
00120 
00121          char *mid = lo + size * ((hi - lo) / size >> 1);
00122 
00123          if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
00124            SWAP (mid, lo, size);
00125          if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
00126            SWAP (mid, hi, size);
00127          else
00128            goto jump_over;
00129          if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
00130            SWAP (mid, lo, size);
00131        jump_over:;
00132 
00133          left_ptr  = lo + size;
00134          right_ptr = hi - size;
00135 
00136          /* Here's the famous ``collapse the walls'' section of quicksort.
00137             Gotta like those tight inner loops!  They are the main reason
00138             that this algorithm runs much faster than others. */
00139          do
00140            {
00141              while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
00142               left_ptr += size;
00143 
00144              while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
00145               right_ptr -= size;
00146 
00147              if (left_ptr < right_ptr)
00148               {
00149                 SWAP (left_ptr, right_ptr, size);
00150                 if (mid == left_ptr)
00151                   mid = right_ptr;
00152                 else if (mid == right_ptr)
00153                   mid = left_ptr;
00154                 left_ptr += size;
00155                 right_ptr -= size;
00156               }
00157              else if (left_ptr == right_ptr)
00158               {
00159                 left_ptr += size;
00160                 right_ptr -= size;
00161                 break;
00162               }
00163            }
00164          while (left_ptr <= right_ptr);
00165 
00166           /* Set up pointers for next iteration.  First determine whether
00167              left and right partitions are below the threshold size.  If so,
00168              ignore one or both.  Otherwise, push the larger partition's
00169              bounds on the stack and continue sorting the smaller one. */
00170 
00171           if ((size_t) (right_ptr - lo) <= max_thresh)
00172             {
00173               if ((size_t) (hi - left_ptr) <= max_thresh)
00174               /* Ignore both small partitions. */
00175                 POP (lo, hi);
00176               else
00177               /* Ignore small left partition. */
00178                 lo = left_ptr;
00179             }
00180           else if ((size_t) (hi - left_ptr) <= max_thresh)
00181            /* Ignore small right partition. */
00182             hi = right_ptr;
00183           else if ((right_ptr - lo) > (hi - left_ptr))
00184             {
00185              /* Push larger left partition indices. */
00186               PUSH (lo, right_ptr);
00187               lo = left_ptr;
00188             }
00189           else
00190             {
00191              /* Push larger right partition indices. */
00192               PUSH (left_ptr, hi);
00193               hi = right_ptr;
00194             }
00195         }
00196     }
00197 
00198   /* Once the BASE_PTR array is partially sorted by quicksort the rest
00199      is completely sorted using insertion sort, since this is efficient
00200      for partitions below MAX_THRESH size. BASE_PTR points to the beginning
00201      of the array to sort, and END_PTR points at the very last element in
00202      the array (*not* one beyond it!). */
00203 
00204 #define min(x, y) ((x) < (y) ? (x) : (y))
00205 
00206   {
00207     char *const end_ptr = &base_ptr[size * (total_elems - 1)];
00208     char *tmp_ptr = base_ptr;
00209     char *thresh = min(end_ptr, base_ptr + max_thresh);
00210     register char *run_ptr;
00211 
00212     /* Find smallest element in first threshold and place it at the
00213        array's beginning.  This is the smallest array element,
00214        and the operation speeds up insertion sort's inner loop. */
00215 
00216     for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
00217       if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
00218         tmp_ptr = run_ptr;
00219 
00220     if (tmp_ptr != base_ptr)
00221       SWAP (tmp_ptr, base_ptr, size);
00222 
00223     /* Insertion sort, running from left-hand-side up to right-hand-side.  */
00224 
00225     run_ptr = base_ptr + size;
00226     while ((run_ptr += size) <= end_ptr)
00227       {
00228        tmp_ptr = run_ptr - size;
00229        while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
00230          tmp_ptr -= size;
00231 
00232        tmp_ptr += size;
00233         if (tmp_ptr != run_ptr)
00234           {
00235             char *trav;
00236 
00237            trav = run_ptr + size;
00238            while (--trav >= run_ptr)
00239               {
00240                 char c = *trav;
00241                 char *hi, *lo;
00242 
00243                 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
00244                   *hi = *lo;
00245                 *hi = c;
00246               }
00247           }
00248       }
00249   }
00250 }