c_cpp/lib/klib/test/ksort_test.c

   1 #include <stdlib.h>
   2 #include <string.h>
   3 #include <stdio.h>
   4 #include <time.h>
   5 #include "ksort.h"
   6
   7 KSORT_INIT_GENERIC(int)
   8
   9 int main(int argc, char *argv[])
  10 {
  11         int i, N = 10000000;
  12         int *array, x;
  13         clock_t t1, t2;
  14         if (argc > 1) N = atoi(argv[1]);
  15         array = (int*)malloc(sizeof(int) * N);
  16
  17         srand48(11);
  18         for (i = 0; i < N; ++i) array[i] = (int)lrand48();
  19         t1 = clock();
  20         x = ks_ksmall(int, N, array, 10500);
  21         t2 = clock();
  22         fprintf(stderr, "ksmall [%d]: %.3lf\n", x, (double)(t2-t1)/CLOCKS_PER_SEC);
  23
  24         srand48(11);
  25         for (i = 0; i < N; ++i) array[i] = (int)lrand48();
  26         t1 = clock();
  27         ks_introsort(int, N, array);
  28         t2 = clock();
  29         fprintf(stderr, "introsort [%d]: %.3lf\n", array[10500], (double)(t2-t1)/CLOCKS_PER_SEC);
  30         for (i = 0; i < N-1; ++i) {
  31                 if (array[i] > array[i+1]) {
  32                         fprintf(stderr, "Bug in introsort!\n");
  33                         exit(1);
  34                 }
  35         }
  36
  37 #ifndef _ALIGNED_ONLY
  38         { // test unaligned ksmall
  39                 srand48(11);
  40                 unsigned char *a;
  41                 int *b;
  42                 a = malloc(N * sizeof(int) + 1);
  43                 b = (int*)(a + 1);
  44                 for (i = 0; i < N; ++i) b[i] = (int)lrand48();
  45                 t1 = clock();
  46                 ks_introsort(int, N, b);
  47                 t2 = clock();
  48                 fprintf(stderr, "introsort [%d]: %.3lf (unaligned: 0x%lx) \n", b[10500], (double)(t2-t1)/CLOCKS_PER_SEC, (size_t)b);
  49         }
  50 #endif
  51
  52         t1 = clock();
  53         ks_introsort(int, N, array);
  54         t2 = clock();
  55         fprintf(stderr, "introsort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
  56
  57         srand48(11);
  58         for (i = 0; i < N; ++i) array[i] = (int)lrand48();
  59         t1 = clock();
  60         ks_combsort(int, N, array);
  61         t2 = clock();
  62         fprintf(stderr, "combsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
  63         for (i = 0; i < N-1; ++i) {
  64                 if (array[i] > array[i+1]) {
  65                         fprintf(stderr, "Bug in combsort!\n");
  66                         exit(1);
  67                 }
  68         }
  69
  70         srand48(11);
  71         for (i = 0; i < N; ++i) array[i] = (int)lrand48();
  72         t1 = clock();
  73         ks_mergesort(int, N, array, 0);
  74         t2 = clock();
  75         fprintf(stderr, "mergesort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
  76         for (i = 0; i < N-1; ++i) {
  77                 if (array[i] > array[i+1]) {
  78                         fprintf(stderr, "Bug in mergesort!\n");
  79                         exit(1);
  80                 }
  81         }
  82
  83         t1 = clock();
  84         ks_mergesort(int, N, array, 0);
  85         t2 = clock();
  86         fprintf(stderr, "mergesort (sorted): %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
  87
  88         srand48(11);
  89         for (i = 0; i < N; ++i) array[i] = (int)lrand48();
  90         t1 = clock();
  91         ks_heapmake(int, N, array);
  92         ks_heapsort(int, N, array);
  93         t2 = clock();
  94         fprintf(stderr, "heapsort: %.3lf\n", (double)(t2-t1)/CLOCKS_PER_SEC);
  95         for (i = 0; i < N-1; ++i) {
  96                 if (array[i] > array[i+1]) {
  97                         fprintf(stderr, "Bug in heapsort!\n");
  98                         exit(1);
  99                 }
 100         }
 101
 102         free(array);
 103         return 0;
 104 }