1 : // ソートテスト その１
    2 : #include <stdio.h>
    3 : #include <stdlib.h>
    4 : #include <time.h>
    5 : #include <assert.h>
    6 : #ifdef __cplusplus
    7 : #include <algorithm>
    8 : #endif
    9 : 
   10 : #ifndef TYPE
   11 : #define TYPE    int
   12 : #endif
   13 : 
   14 : 
   15 : #define swap(a,b)   do { TYPE tmp = (a); (a) = (b); (b) = tmp; } while (0)
   16 : 
   17 : 
   18 : 
   19 : // バブル・ソート
   20 : void bubble_sort(TYPE* data, size_t size) {
   21 :     size_t  i, j;
   22 :     for (i = 0; i < size-1; ++i) {
   23 :         for (j = size; --j > i;) {
   24 :             if (data[j] < data[j-1])
   25 :                 swap(data[j], data[j-1]);
   26 :         }
   27 :     }
   28 : }
   29 : 
   30 : 
   31 : // 選択ソート
   32 : void selection_sort(TYPE* data, size_t size) {
   33 :     size_t  i, j;
   34 :     for (i = 0; i < size; ++i) {
   35 :         size_t  min = i;
   36 :         for (j = i+1; j < size; ++j) {
   37 :             if (data[j] < data[min])
   38 :                 min = j;
   39 :         }
   40 :         swap(data[i], data[min]) ;
   41 :     }
   42 : }
   43 : 
   44 : 
   45 : // 挿入ソート
   46 : void insert_sort(TYPE* data, size_t size) {
   47 :     size_t  i, j;
   48 :     for (i = 1; i < size; ++i) {
   49 :         TYPE    tmp = data[i];
   50 :         for (j = i; j > 0 && tmp < data[j-1]; --j)
   51 :             data[j] = data[j-1];
   52 :         data[j] = tmp;
   53 :     }
   54 : }
   55 : 
   56 : 
   57 : // 挿入ソート (やなうらお版)
   58 : void yane_insert_sort(TYPE* data, size_t size) {
   59 :     size_t i, j;
   60 :     for (i = 1; i < size; i++) {
   61 :         TYPE tmp = data[i];
   62 :         if (data[i-1] > tmp) {
   63 :             j = i;
   64 :             do {
   65 :                 data[j] = data[j-1];
   66 :                 --j;
   67 :             } while ( j > 0 && data[j-1] > tmp);
   68 :             data[j] = tmp;
   69 :         }
   70 :     }
   71 : }
   72 : 
   73 : 
   74 : // 挿入ソート(old) ※2007頃までのwikipediaに載っていたバージョン.
   75 : void old_insert_sort(TYPE* data, size_t size) {
   76 :     size_t  i, j, k;
   77 :     for (i = 0; ++i < size;) {
   78 :         for (j = i, k = i-1; j > 0 && data[j] < data[k]; --j, --k)
   79 :             swap(data[j], data[k]);
   80 :     }
   81 : }
   82 : 
   83 : 
   84 : // コム・ソート
   85 : void comb_sort(TYPE* data, size_t size) {
   86 :     size_t h    = size * 10 / 13;
   87 :     for (;;) {
   88 :         int     swapFlag = 0;
   89 :         size_t  i        = 0;
   90 :         for (i = 0; i + h < size; ++i) {
   91 :             if (data[i + h] < data[i]) {
   92 :                 swap(data[i + h], data[i]);
   93 :                 swapFlag = 1;
   94 :             }
   95 :         }
   96 :         if (h <= 1) {
   97 :             if (!swapFlag)
   98 :                 break;
   99 :         } else {
  100 :             h = h * 10 / 13;
  101 :         }
  102 :     }
  103 : }
  104 : 
  105 : 
  106 : // コム・ソート11
  107 : void comb_sort11(TYPE* data, size_t size) {
  108 :     size_t      h       = size * 10 / 13;
  109 :     for (;;) {
  110 :         size_t  i;
  111 :         int     swapFlag = 0;
  112 :         for (i = 0; i + h < size; ++i) {
  113 :             if (data[i + h] < data[i]) {
  114 :                 swap(data[i + h], data[i]);
  115 :                 swapFlag = 1;
  116 :             }
  117 :         }
  118 :         if (h <= 1) {
  119 :             if (!swapFlag)
  120 :                 break;
  121 :         } else if ((h == 9) | (h == 10)) {
  122 :             h = 11;
  123 :         } else {
  124 :             h = h * 10 / 13;
  125 :         }
  126 :     }
  127 : }
  128 : 
  129 : 
  130 : // 工夫なしのquickソート.
  131 : void quick_sort(TYPE* data, size_t size) {
  132 :     TYPE  m;
  133 :     TYPE *l, *r, *e;
  134 :     if (size <= 1)
  135 :         return;
  136 :     m = data[size / 2];
  137 :     l = data;
  138 :     e = data + size;
  139 :     r = e - 1;
  140 :     for (;;) {
  141 :         while (*l < m)
  142 :             ++l;
  143 :         while (m < *r)
  144 :             --r;
  145 :         if (l >= r)
  146 :             break;
  147 :         swap(*l, *r);
  148 :         ++l;
  149 :     }
  150 :     quick_sort(data, l - data);
  151 :     quick_sort(l   , e - l  );
  152 : }
  153 : 
  154 : 
  155 : 
  156 : // quickソート+挿入ソート (32個以下になったら挿入ソートに切替)
  157 : void ex_quick_sort(TYPE* data, size_t size) {
  158 :     TYPE  m;
  159 :     TYPE *l, *r, *e;
  160 :     if (size <= 32) {
  161 :         if (size <= 1)
  162 :             return;
  163 :         insert_sort(data, size);
  164 :         return;
  165 :     }
  166 :     m = data[size / 2];
  167 :     l = data;
  168 :     e = data + size;
  169 :     r = e - 1;
  170 :     for (;;) {
  171 :         while (*l < m)
  172 :             ++l;
  173 :         while (m < *r)
  174 :             --r;
  175 :         if (l >= r)
  176 :             break;
  177 :         swap(*l, *r);
  178 :         ++l;
  179 :     }
  180 :     ex_quick_sort(data, l - data);
  181 :     ex_quick_sort(l   , e - l  );
  182 : }
  183 : 
  184 : 
  185 : 
  186 : // quickソート+挿入ソート (32個以下になったら挿入ソートに切替)
  187 : void y_quick_sort(TYPE* data, size_t size) {
  188 :     TYPE  m;
  189 :     TYPE *l, *r, *e;
  190 :     if (size <= 32) {
  191 :         if (size <= 1)
  192 :             return;
  193 :         yane_insert_sort(data, size);
  194 :         return;
  195 :     }
  196 :     m = data[size / 2];
  197 :     l = data;
  198 :     e = data + size;
  199 :     r = e - 1;
  200 :     for (;;) {
  201 :         while (*l < m)
  202 :             ++l;
  203 :         while (m < *r)
  204 :             --r;
  205 :         if (l >= r)
  206 :             break;
  207 :         swap(*l, *r);
  208 :         ++l;
  209 :     }
  210 :     y_quick_sort(data, l - data);
  211 :     y_quick_sort(l   , e - l  );
  212 : }
  213 : 
  214 : 
  215 : 
  216 : // qsort用の比較関数.
  217 : int qsort_cmp(const void* a0, const void* b0) {
  218 :     const TYPE* a = (const TYPE* )a0;
  219 :     const TYPE* b = (const TYPE* )b0;
  220 :     return *a - *b;
  221 : }
  222 : 
  223 : 
  224 : 
  225 : // Cライブラリの qsort を使った場合.
  226 : void c_qsort(TYPE* data, size_t size) {
  227 :     qsort(data, size, sizeof(TYPE), qsort_cmp);
  228 : }
  229 : 
  230 : 
  231 : 
  232 : #ifdef __cplusplus
  233 : // std::sort を使ったモノ.
  234 : void std_sort(TYPE* data, size_t size) {
  235 :     std::sort(data, data+size);
  236 : }
  237 : #endif
  238 : 
  239 : 
  240 : 
  241 : // ===========================================================================
  242 : 
  243 : typedef void (*SortFunc)(TYPE*, size_t size);
  244 : 
  245 : void benchmark(const char *name, SortFunc sortFunc, int seed, size_t size, size_t count) {
  246 :     unsigned i, j, ofs = 0;
  247 :     double   elapsed, start_time;
  248 :     TYPE*    data    = (TYPE*) malloc(size * sizeof(TYPE) * count);
  249 :     srand(seed);
  250 :     for (i = 0; i < size * count; ++i)
  251 :         data[i] = rand();
  252 :     start_time  = clock();
  253 :     for (j = 0; j < count; ++j) {
  254 :         sortFunc(&data[ofs], size);
  255 :         ofs        += size;
  256 :     }
  257 :     elapsed    = clock() - start_time;
  258 :     printf("%s:%13.3fμ秒 (%e秒)\n", name, elapsed / (CLOCKS_PER_SEC*count) * 1000000, elapsed / (CLOCKS_PER_SEC*count) );
  259 :     free(data);
  260 : }
  261 : 
  262 : 
  263 : //
  264 : int main(int argc, char **argv) {
  265 :     size_t size  = (argc >= 2) ? atoi(argv[1]) : 100;
  266 :     size_t count = (argc >= 3) ? atoi(argv[2]) : 1;
  267 :     int    all   = (argc >= 4) ? atoi(argv[3]) : 0; // 遅いアルゴリズムも試す時.
  268 :     int    seed  = 1; //time(0);
  269 :     printf("個数 %d, 処理回数 %d\n", size, count);
  270 :     if (all) {  // O(n^2)
  271 :         benchmark("buble sort       ", &bubble_sort     , seed, size, count);
  272 :         benchmark("selection sort   ", &selection_sort  , seed, size, count);
  273 :         benchmark("insert sort      ", &insert_sort     , seed, size, count);
  274 :         benchmark("insert sort(yane)", &yane_insert_sort, seed, size, count);
  275 :     }
  276 :     {           // O(n log n)
  277 :         benchmark("comb sort        ", &comb_sort       , seed, size, count);
  278 :         benchmark("comb sort11      ", &comb_sort11     , seed, size, count);
  279 :         benchmark("quick sort       ", &quick_sort      , seed, size, count);
  280 :         benchmark("quick+insert sort", &ex_quick_sort   , seed, size, count);
  281 :         benchmark("quick+yane-insert", &y_quick_sort    , seed, size, count);
  282 :       #ifdef __cplusplus
  283 :         benchmark("std::sort        ", &std_sort        , seed, size, count);
  284 :       #endif
  285 :         benchmark("qsort            ", &c_qsort         , seed, size, count);
  286 :     }
  287 :     return 0;
  288 : }