1 : // ソートテスト その１
    2 : #include <stdio.h>
    3 : #include <stdlib.h>
    4 : #include <assert.h>
    5 : #ifdef __cplusplus
    6 : #include <algorithm>
    7 : #include <string>
    8 : #endif
    9 : 
   10 : #ifndef TYPE
   11 : #define TYPE    int
   12 : #define QSORT_INT
   13 : #endif
   14 : 
   15 : 
   16 : #define swap(a,b)   do { TYPE tmp = (a); (a) = (b); (b) = tmp; } while (0)
   17 : 
   18 : 
   19 : 
   20 : // バブル・ソート
   21 : void bubble_sort(TYPE* data, size_t size) {
   22 :     size_t  i, j;
   23 :     for (i = 0; i < size-1; ++i) {
   24 :         for (j = size; --j > i;) {
   25 :             if (data[j] < data[j-1])
   26 :                 swap(data[j], data[j-1]);
   27 :         }
   28 :     }
   29 : }
   30 : 
   31 : 
   32 : // 選択ソート
   33 : void selection_sort(TYPE* data, size_t size) {
   34 :     size_t  i, j;
   35 :     for (i = 0; i < size; ++i) {
   36 :         size_t  min = i;
   37 :         for (j = i+1; j < size; ++j) {
   38 :             if (data[j] < data[min])
   39 :                 min = j;
   40 :         }
   41 :         swap(data[i], data[min]) ;
   42 :     }
   43 : }
   44 : 
   45 : 
   46 : // 挿入ソート
   47 : void insert_sort(TYPE* data, size_t size) {
   48 :     size_t  i, j;
   49 :     for (i = 1; i < size; ++i) {
   50 :         TYPE    tmp = data[i];
   51 :         for (j = i; j > 0 && tmp < data[j-1]; --j)
   52 :             data[j] = data[j-1];
   53 :         data[j] = tmp;
   54 :     }
   55 : }
   56 : 
   57 : 
   58 : // 挿入ソート (やなうらお版)
   59 : void yane_insert_sort(TYPE* data, size_t size) {
   60 :     size_t i, j;
   61 :     for (i = 1; i < size; i++) {
   62 :         TYPE tmp = data[i];
   63 :         if (data[i-1] > tmp) {
   64 :             j = i;
   65 :             do {
   66 :                 data[j] = data[j-1];
   67 :                 --j;
   68 :             } while ( j > 0 && data[j-1] > tmp);
   69 :             data[j] = tmp;
   70 :         }
   71 :     }
   72 : }
   73 : 
   74 : 
   75 : // 挿入ソート(old) ※2007頃までのwikipediaに載っていたバージョン.
   76 : void old_insert_sort(TYPE* data, size_t size) {
   77 :     size_t  i, j, k;
   78 :     for (i = 0; ++i < size;) {
   79 :         for (j = i, k = i-1; j > 0 && data[j] < data[k]; --j, --k)
   80 :             swap(data[j], data[k]);
   81 :     }
   82 : }
   83 : 
   84 : 
   85 : // コム・ソート
   86 : void comb_sort(TYPE* data, size_t size) {
   87 :     size_t h    = size * 10 / 13;
   88 :     for (;;) {
   89 :         int     swapFlag = 0;
   90 :         size_t  i        = 0;
   91 :         for (i = 0; i + h < size; ++i) {
   92 :             if (data[i + h] < data[i]) {
   93 :                 swap(data[i + h], data[i]);
   94 :                 swapFlag = 1;
   95 :             }
   96 :         }
   97 :         if (h <= 1) {
   98 :             if (!swapFlag)
   99 :                 break;
  100 :         } else {
  101 :             h = h * 10 / 13;
  102 :         }
  103 :     }
  104 : }
  105 : 
  106 : 
  107 : // コム・ソート11
  108 : void comb_sort11(TYPE* data, size_t size) {
  109 :     size_t      h       = size * 10 / 13;
  110 :     for (;;) {
  111 :         size_t  i;
  112 :         int     swapFlag = 0;
  113 :         for (i = 0; i + h < size; ++i) {
  114 :             if (data[i + h] < data[i]) {
  115 :                 swap(data[i + h], data[i]);
  116 :                 swapFlag = 1;
  117 :             }
  118 :         }
  119 :         if (h <= 1) {
  120 :             if (!swapFlag)
  121 :                 break;
  122 :         } else if ((h == 9) | (h == 10)) {
  123 :             h = 11;
  124 :         } else {
  125 :             h = h * 10 / 13;
  126 :         }
  127 :     }
  128 : }
  129 : 
  130 : 
  131 : // 工夫なしのquickソート.
  132 : void quick_sort(TYPE* data, size_t size) {
  133 :     TYPE  m;
  134 :     TYPE *l, *r, *e;
  135 :     if (size <= 1)
  136 :         return;
  137 :     m = data[size / 2];
  138 :     l = data;
  139 :     e = data + size;
  140 :     r = e - 1;
  141 :     for (;;) {
  142 :         while (*l < m)
  143 :             ++l;
  144 :         while (m < *r)
  145 :             --r;
  146 :         if (l >= r)
  147 :             break;
  148 :         swap(*l, *r);
  149 :         ++l;
  150 :     }
  151 :     quick_sort(data, l - data);
  152 :     quick_sort(l   , e - l  );
  153 : }
  154 : 
  155 : 
  156 : 
  157 : // quickソート+挿入ソート (32個以下になったら挿入ソートに切替)
  158 : void ex_quick_sort(TYPE* data, size_t size) {
  159 :     TYPE  m;
  160 :     TYPE *l, *r, *e;
  161 :     if (size <= 32) {
  162 :         if (size <= 1)
  163 :             return;
  164 :         insert_sort(data, size);
  165 :         return;
  166 :     }
  167 :     m = data[size / 2];
  168 :     l = data;
  169 :     e = data + size;
  170 :     r = e - 1;
  171 :     for (;;) {
  172 :         while (*l < m)
  173 :             ++l;
  174 :         while (m < *r)
  175 :             --r;
  176 :         if (l >= r)
  177 :             break;
  178 :         swap(*l, *r);
  179 :         ++l;
  180 :     }
  181 :     ex_quick_sort(data, l - data);
  182 :     ex_quick_sort(l   , e - l  );
  183 : }
  184 : 
  185 : 
  186 : 
  187 : // quickソート+挿入ソート (32個以下になったら挿入ソートに切替)
  188 : void y_quick_sort(TYPE* data, size_t size) {
  189 :     TYPE  m;
  190 :     TYPE *l, *r, *e;
  191 :     if (size <= 32) {
  192 :         if (size <= 1)
  193 :             return;
  194 :         yane_insert_sort(data, size);
  195 :         return;
  196 :     }
  197 :     m = data[size / 2];
  198 :     l = data;
  199 :     e = data + size;
  200 :     r = e - 1;
  201 :     for (;;) {
  202 :         while (*l < m)
  203 :             ++l;
  204 :         while (m < *r)
  205 :             --r;
  206 :         if (l >= r)
  207 :             break;
  208 :         swap(*l, *r);
  209 :         ++l;
  210 :     }
  211 :     y_quick_sort(data, l - data);
  212 :     y_quick_sort(l   , e - l  );
  213 : }
  214 : 
  215 : 
  216 : #ifndef UNUSE_QSORT
  217 : // qsort用の比較関数.
  218 : int qsort_cmp(const void* a0, const void* b0) {
  219 :     const TYPE* a = (const TYPE* )a0;
  220 :     const TYPE* b = (const TYPE* )b0;
  221 :   #if defined QSORT_INT
  222 :     return *a - *b;
  223 :   #else
  224 :     if (*a < *b)
  225 :         return -1;
  226 :     else if (*a > *b)
  227 :         return 1;
  228 :     return 0;
  229 :   #endif
  230 : }
  231 : 
  232 : 
  233 : 
  234 : // Cライブラリの qsort を使った場合.
  235 : void c_qsort(TYPE* data, size_t size) {
  236 :     qsort(data, size, sizeof(TYPE), qsort_cmp);
  237 : }
  238 : #endif
  239 : 
  240 : 
  241 : #ifdef __cplusplus
  242 : // std::sort を使ったモノ.
  243 : void std_sort(TYPE* data, size_t size) {
  244 :     std::sort(data, data+size);
  245 : }
  246 : #endif
  247 : 
  248 : 
  249 : 
  250 : // ===========================================================================
  251 : #ifdef _WIN32
  252 : #include <windows.h>
  253 : typedef unsigned __int64 PerfCnt_tick_t;
  254 : PerfCnt_tick_t PerfCnt_getTick()    { PerfCnt_tick_t c; QueryPerformanceCounter((LARGE_INTEGER*)&c); return c; }
  255 : PerfCnt_tick_t PerfCnt_tickPerSec() { static PerfCnt_tick_t s = 0; if (!s) QueryPerformanceFrequency((LARGE_INTEGER*)&s); return s; }
  256 : #else
  257 : #include <time.h>
  258 : typedef clock_t PerfCnt_tick_t;
  259 : #define PerfCnt_getTick()           clock()
  260 : #define PerfCnt_tickPerSec()        CLOCKS_PER_SEC
  261 : #endif
  262 : 
  263 : 
  264 : // ===========================================================================
  265 : typedef void (*SortFunc)(TYPE*, size_t size);
  266 : 
  267 : double benchmark(SortFunc sortFunc, size_t size, size_t count, int seed) {
  268 :     unsigned        i, j, ofs = 0;
  269 :     PerfCnt_tick_t  elapsed, start_time;
  270 :     TYPE*           data    = (TYPE*) calloc(1, size * count * sizeof(TYPE) + 16);
  271 :     if (data == 0) { printf("not enough memory.\n"); exit(1); }
  272 :     srand(seed);
  273 :     for (i = 0; i < size * count; ++i)
  274 :         data[i] = rand();
  275 :     start_time  = PerfCnt_getTick();
  276 :     for (j = 0; j < count; ++j) {
  277 :         sortFunc(&data[ofs], size);
  278 :         ofs        += size;
  279 :     }
  280 :     elapsed    = PerfCnt_getTick() - start_time;
  281 :     free(data);
  282 :     return elapsed * 1.0 / (PerfCnt_tickPerSec()*count);
  283 : }
  284 : 
  285 : 
  286 : 
  287 : struct St {
  288 :     size_t      size;
  289 :     size_t      count;
  290 :     int         on2flag;
  291 :     double      elaped[11];
  292 : };
  293 : 
  294 : 
  295 : //
  296 : int main(int argc, char *argv[]) {
  297 :     int          on2flag  = 1;
  298 :     St           st[128];
  299 :     const char*  ttl[12] = {0};
  300 :     unsigned     i;
  301 :     unsigned     n    = 0;
  302 :     unsigned     seed = 1;  //time(0);
  303 :     if (argc < 3) {
  304 :         printf("usage> sort_test1 [-na] size1 count1 [size2 count2 ...]\n"
  305 :                " -na 以降O(n^2)なアルゴリズム無視\n"
  306 :         );
  307 :         return 1;
  308 :     }
  309 :     for (i = 1; i < argc && n < 128; i += 2) {
  310 :         if (strcmp(argv[i],"-na") == 0) {
  311 :             on2flag  = 0;
  312 :             ++i;
  313 :         }
  314 :         memset(&st[n], 0, sizeof st[0]);
  315 :         st[n].size    = (i   < argc) ? atoi(argv[i+0]) : 10;
  316 :         st[n].count   = (i+1 < argc) ? atoi(argv[i+1]) : 1;
  317 :         st[n].on2flag = on2flag;
  318 :         ++n;
  319 :     }
  320 : 
  321 :     printf("\nsort_test1 : sizeof(TYPE)=%dbytes\n", sizeof(TYPE));
  322 :     for (i = 0; i < n; ++i) {
  323 :         St* t = &st[i];
  324 :         printf("個数 %9d, 処理回数 %9d\n", t->size, t->count);
  325 :         if (t->on2flag) {   // O(n^2)
  326 :             t->elaped[ 0] = benchmark(&bubble_sort     , t->size, t->count, seed);  ttl[ 0] = "bubble sort       ";
  327 :             t->elaped[ 1] = benchmark(&selection_sort  , t->size, t->count, seed);  ttl[ 1] = "selection sort    ";
  328 :             t->elaped[ 2] = benchmark(&insert_sort     , t->size, t->count, seed);  ttl[ 2] = "insert sort       ";
  329 :             t->elaped[ 3] = benchmark(&yane_insert_sort, t->size, t->count, seed);  ttl[ 3] = "insert sort(yane) ";
  330 :         }
  331 :         {
  332 :             t->elaped[ 4] = benchmark(&comb_sort      , t->size, t->count, seed);   ttl[ 4] = "comb sort         ";
  333 :             t->elaped[ 5] = benchmark(&comb_sort11    , t->size, t->count, seed);   ttl[ 5] = "comb sort11       ";
  334 :             t->elaped[ 6] = benchmark(&quick_sort     , t->size, t->count, seed);   ttl[ 6] = "quick sort        ";
  335 :             t->elaped[ 7] = benchmark(&ex_quick_sort  , t->size, t->count, seed);   ttl[ 7] = "quick+insert sort ";
  336 :             t->elaped[ 8] = benchmark(&y_quick_sort   , t->size, t->count, seed);   ttl[ 8] = "quick+insert(yane)";
  337 :           #ifdef __cplusplus
  338 :             t->elaped[ 9] = benchmark(&std_sort       , t->size, t->count, seed);   ttl[ 9] = "std::sort         ";
  339 :           #endif
  340 :           #ifndef UNUSE_QSORT
  341 :             t->elaped[10] = benchmark(&c_qsort        , t->size, t->count, seed);   ttl[10] = "qsort             ";
  342 :           #endif
  343 :         }
  344 :     }
  345 :     ttl[11] = 0;
  346 : 
  347 :     printf("\n");
  348 :     printf("%18s ,", "個数");
  349 :     for (unsigned i = 0; i < n; ++i) {
  350 :         printf("%9d個,", st[i].size);
  351 :     };
  352 :     printf("\n");
  353 :     for (unsigned j = 0; j < 11; ++j) {
  354 :         if (ttl[j] == 0)
  355 :             continue;
  356 :         printf("%-18s ,", ttl[j]);
  357 :         for (unsigned i = 0; i < n; ++i) {
  358 :             double e = st[i].elaped[j]*1000000.0;
  359 :             if (e > 0)
  360 :                 printf("%11.3f,", e);
  361 :             else
  362 :                 printf("%11s,", "---");
  363 :         };
  364 :         printf("\n");
  365 :     }
  366 :     return 0;
  367 : }