tests/benchs/quicksort.c

   1
   2 /* function quicksort: sorting algorithm of n*log(n) complexity
   3    ran 10000000 times on 3 lists of size 100 */
   4
   5
   6 int a1[] =
   7   {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21,
   8    22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40,
   9    41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
  10    60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78,
  11    79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97,
  12    98, 99};
  13 int a2[] =
  14   {99, 98, 97, 96, 95, 94, 93, 92, 91, 90, 89, 88, 87, 86, 85, 84, 83, 82, 81,
  15    80, 79, 78, 77, 76, 75, 74, 73, 72, 71, 70, 69, 68, 67, 66, 65, 64, 63, 62,
  16    61, 60, 59, 58, 57, 56, 55, 54, 53, 52, 51, 50, 49, 48, 47, 46, 45, 44, 43,
  17    42, 41, 40, 39, 38, 37, 36, 35, 34, 33, 32, 31, 30, 29, 28, 27, 26, 25, 24,
  18    23, 22, 21, 20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3,
  19    2, 1, 0};
  20
  21 void swap (int a[], int i, int j) {
  22   int t;
  23   t = a[i] ; a[i] = a[j] ; a[j] = t;
  24 }
  25
  26 int partition (int a[], int l, int r) {
  27    int pivot, i, j;
  28    pivot = a[l];
  29    i = l; j = r+1;
  30
  31    while (1) {
  32      do ++i; while (a[i] <= pivot && i <= r);
  33      do --j; while (a[j] > pivot);
  34      if (i >= j) break;
  35      swap(a, i, j);
  36    }
  37    swap(a, l, j);
  38    return j;
  39 }
  40
  41 void quickSort (int a[], int l, int r) {
  42    int j;
  43
  44    if (l < r) {
  45      j = partition(a, l, r);
  46      quickSort(a, l, j-1);
  47      quickSort(a, j+1, r);
  48    }
  49 }
  50
  51 void copy (int dest[], int src[], int size) {
  52   int i;
  53
  54   for (i = 0 ; i < size ; i++)
  55     dest[i] = src[i];
  56 }
  57
  58 void run (int a[]) {
  59   int size, tab[100];
  60
  61   size = sizeof(a) / sizeof(int);
  62   copy(tab, a, size);
  63   quickSort(tab, 0, size-1);
  64 }
  65
  66 int main () {
  67   int i;
  68   int a3[] =
  69     {-21, 19, -26, -62, -72, 33, -14, 20, 85, 92, -26, -33, 38, -14, -88, -35,
  70      -51, 29, -84, -98, -92, -60, -52, 53, 53, -11, -99, 72, -55, 90, -83, 98,
  71      29, -25, -32, -33, -98, 14, -86, 99, 77, -38, -1, -7, -98, 57, 5, -64, 72,
  72      60, -5, -66, -7, -84, -97, 92, 2, 11, 70, -27, -56, -16, -81, 86, 27, 24,
  73      68, -54, -15, -45, 60, 25, -31, 67, 7, -14, -41, -67, 51, -27, -1, -98,
  74      -97, -16, -41, 33, -8, -45, 48, -44, -1, 56, -70, 59, -60, 64, 5, 32, 86,
  75      -72};
  76
  77   for (i = 0 ; i < 10000000 ; i++) {
  78     run(a1);
  79     run(a2);
  80     run(a3);
  81   }
  82
  83   return 0;
  84 }