lib-src/sort/qa.cc

   1 #include <stdio.h>
   2 #include <string.h>
   3 #include <assert.h>
   4 #include <AD/sort/bubble.h>     // bubble sort
   5 #include <AD/sort/insort.h>     // Insertion sort
   6 #include <AD/sort/heapsort.h>   // Heap sort
   7 #include <AD/sort/mergesrt.h>   // Merge sort
   8 #include <AD/sort/quicksrt.h>   // Quicker sort
   9 #include <AD/sort/radixsrt.h>   // Radix sort
  10 #include <AD/sort/shellsrt.h>   // Shell sort
  11 #include <AD/sort/bubble2.h>    // bubble sort
  12 #include <AD/sort/insort2.h>    // Insertion sort
  13 #include <AD/sort/heapsrt2.h>   // Heap sort
  14 #include <AD/sort/shellst2.h>   // Shell sort
  15
  16 int sorted(const char * names[], int size)
  17 {
  18    for (int i = 0; i < size - 1; i++)
  19       if (strcmp(names[i],names[i+1]) >= 0) return 0;
  20    return 1;
  21 }
  22
  23 int rev_sorted(const char * names[], int size)
  24 {
  25    for (int i = 0; i < size - 1; i++)
  26       if (strcmp(names[i],names[i+1]) <= 0) return 0;
  27    return 1;
  28 }
  29
  30 void pr(const char * algorithm, const char * names[], int size)
  31 {   printf("%s: [ ",algorithm);
  32     for (int i = 0; i < size; i++) {
  33        printf("%s",names[i]);
  34        if (i < size - 1) printf(", ");
  35     }
  36     printf(" ]\n");
  37 }
  38
  39 int main(int argc, char * argv[])
  40 {  static const char * people[] =
  41       { "Godel", "Post", "Russel", "Church", "Turing",
  42         "Thue", "von Neuman", "Davis", "Scott", "Rogers",
  43         "Newton", "Euler", "Markov", "Herbrand", "Bucchi",
  44         "Kleene", "Skolem", "Martin Lof", "Zemelo", "Fraenkel",
  45         "Euclid", "Rice", "Cantor", "Dedekind", "Taylor",
  46         "Fermat", "Hilbert", "Riemann", "Jacobi", "Dirichlet"
  47       };
  48
  49     const char * names[sizeof(people)/sizeof(people[0])];
  50
  51     memcpy(names,people,sizeof(people));
  52     heapSort(const char *, names, sizeof(names)/sizeof(names[0]),
  53              strcmp(key,names[i]) < 0);
  54     pr ("Heap sort",names, sizeof(names)/sizeof(names[0]));
  55     assert ( sorted(names, sizeof(names)/sizeof(names[0]) ) );
  56
  57     memcpy(names,people,sizeof(people));
  58     heapSort(const char *, names, sizeof(names)/sizeof(names[0]),
  59              strcmp(key,names[i]) > 0);
  60     pr ("Heap sort",names, sizeof(names)/sizeof(names[0]));
  61     assert ( rev_sorted(names, sizeof(names)/sizeof(names[0]) ) );
  62
  63     memcpy(names,people,sizeof(people));
  64     bubbleSort(const char *, names, sizeof(names)/sizeof(names[0]),
  65                strcmp(names[i],names[i+1]) < 0);
  66     pr ("Bubble sort",names, sizeof(names)/sizeof(names[0]));
  67     assert ( sorted(names, sizeof(names)/sizeof(names[0]) ) );
  68
  69     memcpy(names,people,sizeof(people));
  70     bubbleSort(const char *, names, sizeof(names)/sizeof(names[0]),
  71                strcmp(names[i],names[i+1]) > 0);
  72     pr ("Bubble sort",names, sizeof(names)/sizeof(names[0]));
  73     assert ( rev_sorted(names, sizeof(names)/sizeof(names[0]) ) );
  74
  75     memcpy(names,people,sizeof(people));
  76     shellSort(const char *, names, sizeof(names)/sizeof(names[0]),
  77               strcmp(key,names[i]) < 0);
  78     pr ("Shell sort",names, sizeof(names)/sizeof(names[0]));
  79     assert ( sorted(names, sizeof(names)/sizeof(names[0]) ) );
  80
  81     memcpy(names,people,sizeof(people));
  82     shellSort(const char *, names, sizeof(names)/sizeof(names[0]),
  83               strcmp(key,names[i]) > 0);
  84     pr ("Shell sort",names, sizeof(names)/sizeof(names[0]));
  85     assert ( rev_sorted(names, sizeof(names)/sizeof(names[0]) ) );
  86
  87     memcpy(names,people,sizeof(people));
  88     insertionSort(const char *, names, sizeof(names)/sizeof(names[0]),
  89               strcmp(key,names[i]) < 0);
  90     pr ("Insertion sort",names, sizeof(names)/sizeof(names[0]));
  91     assert ( sorted(names, sizeof(names)/sizeof(names[0]) ) );
  92
  93     memcpy(names,people,sizeof(people));
  94     insertionSort(const char *, names, sizeof(names)/sizeof(names[0]),
  95               strcmp(key,names[i]) > 0);
  96     pr ("Insertion sort",names, sizeof(names)/sizeof(names[0]));
  97     assert ( rev_sorted(names, sizeof(names)/sizeof(names[0]) ) );
  98
  99     memcpy(names,people,sizeof(people));
 100     quickSort(const char *, names, sizeof(names)/sizeof(names[0]),
 101               strcmp(key,A[i]) < 0);
 102     pr ("Quick sort",names, sizeof(names)/sizeof(names[0]));
 103     assert ( sorted(names, sizeof(names)/sizeof(names[0]) ) );
 104
 105     memcpy(names,people,sizeof(people));
 106     quickSort(const char *, names, sizeof(names)/sizeof(names[0]),
 107               strcmp(key,A[i]) > 0);
 108     pr ("Quick sort",names, sizeof(names)/sizeof(names[0]));
 109     assert ( rev_sorted(names, sizeof(names)/sizeof(names[0]) ) );
 110
 111
 112     printf("OK\n");
 113     return 0;
 114 }