1 : // ソートテスト その２
    2 : #include <stdio.h>
    3 : #include <stdlib.h>
    4 : #include <time.h>
    5 : #include <assert.h>
    6 : #include <algorithm>
    7 : #include <functional>
    8 : #include <vector>
    9 : #include <string>
   10 : 
   11 : 
   12 : template<typename BidiIte> inline
   13 : void insert_sort(const BidiIte& first, const BidiIte& last)
   14 : {
   15 :     typedef typename std::iterator_traits<BidiIte>::value_type  T;
   16 :     using std::iter_swap;
   17 : 
   18 :     BidiIte i = first;
   19 :     while (++i != last) {
   20 :         T       tmp( *i );
   21 :         BidiIte j = i;
   22 :         BidiIte k = i;
   23 :         --k;
   24 :         while (j != first && tmp < *k) {
   25 :             *j = *k;
   26 :             --j;
   27 :             --k;
   28 :         }
   29 :         *j = tmp;
   30 :     }
   31 : }
   32 : 
   33 : 
   34 : template<typename BidiIte, class C> inline
   35 : void insert_sort(const BidiIte& first, const BidiIte& last, C cmp)
   36 : {
   37 :     typedef typename std::iterator_traits<BidiIte>::value_type  T;
   38 :     using std::iter_swap;
   39 : 
   40 :     BidiIte i = first;
   41 :     while (++i != last) {
   42 :         T       tmp( *i );
   43 :         BidiIte j = i;
   44 :         BidiIte k = i;
   45 :         --k;
   46 :         while (j != first && cmp(tmp, *k)) {
   47 :             *j = *k;
   48 :             --j;
   49 :             --k;
   50 :         }
   51 :         *j = tmp;
   52 :     }
   53 : }
   54 : 
   55 : 
   56 : template<typename RAIte>
   57 : void quick_sort(RAIte first, RAIte last)
   58 : {
   59 :     typedef typename std::iterator_traits<RAIte>::value_type    T;
   60 :     using std::iter_swap;
   61 : 
   62 :     std::size_t     size = last - first;
   63 :     if (size <= 32) {
   64 :         if (size > 1)
   65 :             insert_sort(first, last);
   66 :         return;
   67 :     }
   68 :     const T m( *( first + size / 2 ) );
   69 :     RAIte   l = first;
   70 :     RAIte   r = last;
   71 :     for (;;) {
   72 :         while (*l < m)
   73 :             ++l;
   74 :         do {
   75 :             --r;
   76 :         } while (m < *r);
   77 :         if (!(l < r))
   78 :             break;
   79 :         iter_swap(l, r);
   80 :         ++l;
   81 :     }
   82 :     quick_sort(first, l   );
   83 :     quick_sort(l    , last);
   84 : }
   85 : 
   86 : 
   87 : 
   88 : template<typename RAIte, class C>
   89 : void quick_sort(RAIte first, RAIte last, C cmp)
   90 : {
   91 :     typedef typename std::iterator_traits<RAIte>::value_type    T;
   92 :     using std::iter_swap;
   93 : 
   94 :     std::size_t     size = last - first;
   95 :     if (size <= 32) {
   96 :         if (size > 1)
   97 :             insert_sort(first, last, cmp);
   98 :         return;
   99 :     }
  100 :     const T m( *( first + size / 2 ) );
  101 :     RAIte   l = first;
  102 :     RAIte   r = last;
  103 :     for (;;) {
  104 :         while (cmp(*l, m))
  105 :             ++l;
  106 :         do {
  107 :             --r;
  108 :         } while (cmp(m, *r));
  109 :         if (!(l < r))
  110 :             break;
  111 :         iter_swap(l, r);
  112 :         ++l;
  113 :     }
  114 :     quick_sort(first, l   , cmp);
  115 :     quick_sort(l    , last, cmp);
  116 : }
  117 : 
  118 : 
  119 : 
  120 : template<typename BidiIte>
  121 : void bidi_quick_sort(BidiIte first, BidiIte last)
  122 : {
  123 :     typedef typename std::iterator_traits<BidiIte>::value_type  T;
  124 : 
  125 :     using std::iter_swap;
  126 :     std::size_t size = std::size_t(std::distance(first, last));
  127 :     if (size <= 32) {
  128 :         if (size > 1)
  129 :             insert_sort(first, last);
  130 :         return;
  131 :     }
  132 :     BidiIte ite( first );
  133 :     std::advance( ite, size / 2 );
  134 :     const T m( *ite );
  135 :     BidiIte     l = first;
  136 :     BidiIte     r = last;
  137 :     std::size_t lc = 0;
  138 :     std::size_t rc = size;
  139 :     for (;;) {
  140 :         while (*l < m)
  141 :             ++l, ++lc;
  142 :         do {
  143 :             --r, --rc;
  144 :         } while (m < *r);
  145 :         if (lc >= rc)
  146 :             break;
  147 :         iter_swap(l, r);
  148 :         ++l, ++lc;
  149 :     }
  150 :     bidi_quick_sort(first, l   );
  151 :     bidi_quick_sort(l    , last);
  152 : }
  153 : 
  154 : 
  155 : 
  156 : template<typename BidiIte, class C>
  157 : void bidi_quick_sort(BidiIte first, BidiIte last, C cmp)
  158 : {
  159 :     typedef typename std::iterator_traits<BidiIte>::value_type  T;
  160 : 
  161 :     using std::iter_swap;
  162 :     std::size_t size = std::size_t(std::distance(first, last));
  163 :     if (size <= 32) {
  164 :         if (size > 1)
  165 :             insert_sort(first, last, cmp);
  166 :         return;
  167 :     }
  168 :     BidiIte ite( first );
  169 :     std::advance( ite, size / 2 );
  170 :     const T m( *ite );
  171 :     BidiIte     l = first;
  172 :     BidiIte     r = last;
  173 :     std::size_t lc = 0;
  174 :     std::size_t rc = size;
  175 :     for (;;) {
  176 :         while (cmp(*l, m))
  177 :             ++l, ++lc;
  178 :         do {
  179 :             --r, --rc;
  180 :         } while (cmp(m, *r));
  181 :         if (lc >= rc)
  182 :             break;
  183 :         iter_swap(l, r);
  184 :         ++l, ++lc;
  185 :     }
  186 :     bidi_quick_sort(first, l   , cmp);
  187 :     bidi_quick_sort(l    , last, cmp);
  188 : }
  189 : 
  190 : 
  191 : 
  192 : // ===========================================================================
  193 : #ifdef _WIN32
  194 : #include <windows.h>
  195 : typedef unsigned __int64 PerfCnt_tick_t;
  196 : PerfCnt_tick_t PerfCnt_getTick()    { PerfCnt_tick_t c; QueryPerformanceCounter((LARGE_INTEGER*)&c); return c; }
  197 : PerfCnt_tick_t PerfCnt_tickPerSec() { static PerfCnt_tick_t s = 0; if (!s) QueryPerformanceFrequency((LARGE_INTEGER*)&s); return s; }
  198 : #else
  199 : #include <time.h>
  200 : typedef clock_t PerfCnt_tick_t;
  201 : #define PerfCnt_getTick()           clock()
  202 : #define PerfCnt_tickPerSec()        CLOCKS_PER_SEC
  203 : #endif
  204 : 
  205 : 
  206 : // ===========================================================================
  207 : 
  208 : template<typename T>
  209 : T random() {
  210 :     return T(rand());
  211 : }
  212 : 
  213 : template<>
  214 : std::string random<std::string>() {
  215 :     char buf[128];
  216 :     sprintf(buf, "%d%d%d", rand(),rand(),rand());
  217 :     return std::string(buf);
  218 : }
  219 : 
  220 : 
  221 : #define BENCHMARK(name,SORT,T,cmpFlg,size,count,seed) do {          \
  222 :     std::vector<T> data;                                            \
  223 :     srand(seed);                                                    \
  224 :     for (unsigned i = 0; i < size * count; ++i) {                   \
  225 :         data.push_back(random<T>());                                \
  226 :     }                                                               \
  227 :     unsigned                ofs        = 0;                         \
  228 :     PerfCnt_tick_t  start_time = PerfCnt_getTick();                 \
  229 :     for (unsigned j = 0; j < count; ++j) {                          \
  230 :         if (cmpFlg == 0)                                            \
  231 :             SORT(&data[ofs], &data[ofs]+size);                      \
  232 :         else                                                        \
  233 :             SORT(&data[ofs], &data[ofs]+size, std::less<T>() );     \
  234 :         ofs        += size;                                         \
  235 :     }                                                               \
  236 :     PerfCnt_tick_t  elapsed    = PerfCnt_getTick() - start_time;    \
  237 :     printf("%s:%13.3fμ秒 (%e秒)\n", name                           \
  238 :             , elapsed * 1000000.0 / (PerfCnt_tickPerSec() * count)  \
  239 :             , elapsed / double(PerfCnt_tickPerSec() * count) );     \
  240 : } while (0)
  241 : 
  242 : 
  243 : #ifndef TYPE
  244 : #define TYPE    int
  245 : #endif
  246 : 
  247 : //
  248 : int main(int argc, char **argv) {
  249 :     size_t  size  = (argc >= 2) ? atoi(argv[1]) : 100;
  250 :     size_t  count = (argc >= 3) ? atoi(argv[2]) : 1;
  251 :     int    seed  = 1; //time(0);
  252 :     printf("個数 %d, 処理回数 %d\n", size, count);
  253 :     BENCHMARK("std::sort(arg2)      ", std::sort,       TYPE, 0, size, count, seed);
  254 :     BENCHMARK("std::sort(arg3)      ", std::sort,       TYPE, 1, size, count, seed);
  255 :     BENCHMARK("quick sort(arg2)     ", quick_sort,      TYPE, 0, size, count, seed);
  256 :     BENCHMARK("quick sort(arg3)     ", quick_sort,      TYPE, 1, size, count, seed);
  257 :     BENCHMARK("quick sort:bidi(arg2)", bidi_quick_sort, TYPE, 0, size, count, seed);
  258 :     BENCHMARK("quick sort:bidi(arg3)", bidi_quick_sort, TYPE, 1, size, count, seed);
  259 :     return 0;
  260 : }