test/heapsort.c

   1 /* -*- mode: c -*-
   2  * $Id$
   3  * http://www.bagley.org/~doug/shootout/
   4  */
   5
   6 #include <stdlib.h>
   7 #include <math.h>
   8 #include <stdio.h>
   9
  10 #define IM 139968
  11 #define IA   3877
  12 #define IC  29573
  13
  14 double
  15 gen_random(double max) {
  16     static long last = 42;
  17     return( max * (last = (last * IA + IC) % IM) / IM );
  18 }
  19
  20 void
  21 heapsort(int n, double *ra) {
  22     int i, j;
  23     int ir = n;
  24     int l = (n >> 1) + 1;
  25     double rra;
  26
  27     for (;;) {
  28         if (l > 1) {
  29             rra = ra[--l];
  30         } else {
  31             rra = ra[ir];
  32             ra[ir] = ra[1];
  33             if (--ir == 1) {
  34                 ra[1] = rra;
  35                 return;
  36             }
  37         }
  38
  39         i = l;
  40         j = l << 1;
  41         while (j <= ir) {
  42             if (j < ir && ra[j] < ra[j+1]) {
  43               ++j;
  44             }
  45             if (rra < ra[j]) {
  46                 ra[i] = ra[j];
  47                 j += (i = j);
  48             } else {
  49                 j = ir + 1;
  50             }
  51         }
  52         ra[i] = rra;
  53     }
  54 }
  55
  56 int
  57 main(int argc, char *argv[]) {
  58     int N = ((argc == 2) ? atoi(argv[1]) : 10);
  59     double *ary;
  60     int i;
  61
  62     /* create an array of N random doubles */
  63     ary = (double *)malloc((N+1) * sizeof(double));
  64     for (i=1; i<=N; i++) {
  65         ary[i] = gen_random(1);
  66     }
  67
  68     heapsort(N, ary);
  69
  70     printf("%f\n", ary[N]);
  71
  72     free(ary);
  73     return(0);
  74 }
  75