benchmarks/qsort/qsort_main.c

   1 // See LICENSE for license details.
   2
   3 //**************************************************************************
   4 // Quicksort benchmark
   5 //--------------------------------------------------------------------------
   6 //
   7 // This benchmark uses quicksort to sort an array of integers. The
   8 // implementation is largely adapted from Numerical Recipes for C. The
   9 // input data (and reference data) should be generated using the
  10 // qsort_gendata.pl perl script and dumped to a file named
  11 // dataset1.h.
  12
  13 #include "util.h"
  14 #include <string.h>
  15 #include <assert.h>
  16
  17 // The INSERTION_THRESHOLD is the size of the subarray when the
  18 // algorithm switches to using an insertion sort instead of
  19 // quick sort.
  20
  21 #define INSERTION_THRESHOLD 10
  22
  23 // NSTACK is the required auxiliary storage.
  24 // It must be at least 2*lg(DATA_SIZE)
  25
  26 #define NSTACK 50
  27
  28 //--------------------------------------------------------------------------
  29 // Input/Reference Data
  30
  31 #define type int
  32 #include "dataset1.h"
  33
  34 // Swap macro for swapping two values.
  35
  36 #define SWAP(a,b) do { typeof(a) temp=(a);(a)=(b);(b)=temp; } while (0)
  37 #define SWAP_IF_GREATER(a, b) do { if ((a) > (b)) SWAP(a, b); } while (0)
  38
  39 //--------------------------------------------------------------------------
  40 // Quicksort function
  41
  42 static void insertion_sort(size_t n, type arr[])
  43 {
  44   type *i, *j;
  45   type value;
  46   for (i = arr+1; i < arr+n; i++)
  47   {
  48     value = *i;
  49     j = i;
  50     while (value < *(j-1))
  51     {
  52       *j = *(j-1);
  53       if (--j == arr)
  54         break;
  55     }
  56     *j = value;
  57   }
  58 }
  59
  60 static void selection_sort(size_t n, type arr[])
  61 {
  62   for (type* i = arr; i < arr+n-1; i++)
  63     for (type* j = i+1; j < arr+n; j++)
  64       SWAP_IF_GREATER(*i, *j);
  65 }
  66
  67 void sort(size_t n, type arr[])
  68 {
  69   type* ir = arr+n;
  70   type* l = arr+1;
  71   type* stack[NSTACK];
  72   type** stackp = stack;
  73
  74   for (;;)
  75   {
  76     // Insertion sort when subarray small enough.
  77     if ( ir-l < INSERTION_THRESHOLD )
  78     {
  79       insertion_sort(ir - l + 1, l - 1);
  80
  81       if ( stackp == stack ) break;
  82
  83       // Pop stack and begin a new round of partitioning.
  84       ir = *stackp--;
  85       l = *stackp--;
  86     }
  87     else
  88     {
  89       // Choose median of left, center, and right elements as
  90       // partitioning element a. Also rearrange so that a[l-1] <= a[l] <= a[ir-].
  91       SWAP(arr[((l-arr) + (ir-arr))/2-1], l[0]);
  92       SWAP_IF_GREATER(l[-1], ir[-1]);
  93       SWAP_IF_GREATER(l[0], ir[-1]);
  94       SWAP_IF_GREATER(l[-1], l[0]);
  95
  96       // Initialize pointers for partitioning.
  97       type* i = l+1;
  98       type* j = ir;
  99
 100       // Partitioning element.
 101       type a = l[0];
 102
 103       for (;;) {                    // Beginning of innermost loop.
 104         while (*i++ < a);           // Scan up to find element > a.
 105         while (*(j-- - 2) > a);     // Scan down to find element < a.
 106         if (j < i) break;           // Pointers crossed. Partitioning complete.
 107         SWAP(i[-1], j[-1]);         // Exchange elements.
 108       }                             // End of innermost loop.
 109
 110       // Insert partitioning element.
 111       l[0] = j[-1];
 112       j[-1] = a;
 113       stackp += 2;
 114
 115       // Push pointers to larger subarray on stack,
 116       // process smaller subarray immediately.
 117
 118       if ( ir-i+1 >= j-l )
 119       {
 120         stackp[0] = ir;
 121         stackp[-1] = i;
 122         ir = j-1;
 123       }
 124       else
 125       {
 126         stackp[0] = j-1;
 127         stackp[-1] = l;
 128         l = i;
 129       }
 130     }
 131   }
 132 }
 133
 134 //--------------------------------------------------------------------------
 135 // Main
 136
 137 int main( int argc, char* argv[] )
 138 {
 139 #if PREALLOCATE
 140   // If needed we preallocate everything in the caches
 141   sort(DATA_SIZE, verify_data);
 142   if (verify(DATA_SIZE, input_data, input_data))
 143     return 1;
 144 #endif
 145
 146   // Do the sort
 147   setStats(1);
 148   sort( DATA_SIZE, input_data );
 149   setStats(0);
 150
 151   // Check the results
 152   return verify( DATA_SIZE, input_data, verify_data );
 153 }