|
| |
※「セキュリティ保護のため...」というメッセージが出る方・日本語が入力できない方へ
(6)コムソート
コムソート(Comb Sort)は、実は遅いことで有名なバブルソートの改良版で
ある。ところが、この改良版が実はヒープソート並みに高速なのである。
このソートは「髪を櫛でとく時に最初粗い櫛でといて、そのあと細かい櫛
でとくように」データをまず大雑把に並べて、そのあと少しずつ、細かい
部分まできれいに順序に並ぶようにしていく。
実際のロジックについては専門的になるので省略するが、コーディングは
バブルソートとほとんど変わらず簡単であり、メモリーも消費しないし、
ヒープソートのような、大がかりな構造体も不要である。
唯一の欠点は、このロジックを知らない人がこのコーディング（結構トリ
ッキーである）を見たとき、なぜ、これでソートになるのか？というのが、
まず理解できないことであろう。10年ほど前に発見された新しいソート。
【Coding Sample】(Comb Sort)
void CSortDlg::CombSort()
{
int i,j;
int sort_cnt,sort_gap,sort_sw;
sort_gap = sort_cnt = m_dcnt;
if (sort_cnt<=1)
goto loop_e;
loop_1:
sort_gap = sort_gap * 10 / 13;
if (sort_gap == 0)
sort_gap = 1;
sort_sw = 0;
i = 0;
loop_2:
j = i + sort_gap;
if (m_data[i] > m_data[j])
{
long x;
x = m_data[i];
m_data[i] = m_data[j];
m_data[j] = x;
sort_sw = 1;
}
if (j + 1 < sort_cnt)
{
i++;
goto loop_2;
}
if (sort_sw == 1 || sort_gap > 1)
goto loop_1;
loop_e:
return;
}
【実行時間】(Pentium-75MHz VisualC++5.0 Release Mode)
件数 乱順 正順 逆順
CombSort(r) 1000 0.00000 0.00000 0.00000
CombSort(r) 10000 0.05000 0.06000 0.05000
CombSort(r) 30000 0.27000 0.17000 0.16000
CombSort(r) 100000 0.99000 0.66000 0.71000
CombSort(r) 300000 3.79000 2.31000 2.59000
CombSort(r) 1000000 13.51000 8.95000 9.67000
CombSort(r) 3000000 43.77000 29.60000 31.53000
さて、この高速なCombSortに更に改良型が存在する。それは櫛のサイズが
9または10になった時、強制的に11に戻してしまうという方法である。これ
が何の意味があるのかというと、要するに
9→6→4→3→2→1
10→7→5→3→2→1
11→8→6→4→3→2→1
となるので、11に戻した方が、8,6,4 というキレイに梳ける櫛になってく
れるのである。
【Coding Sample】(Comb Sort Revised)
void CSortDlg::CombSort2()
{
int i,j;
int sort_cnt,sort_gap,sort_sw;
sort_gap = sort_cnt = m_dcnt;
if (sort_cnt<=1)
goto loop_e;
loop_1:
sort_gap = sort_gap * 10 / 13;
if (sort_gap == 0)
sort_gap = 1;
else if (sort_gap == 9 || sort_gap == 10)
sort_gap = 11;
sort_sw = 0;
i = 0;
loop_2:
j = i + sort_gap;
if (m_data[i] > m_data[j])
{
long x;
x = m_data[i];
m_data[i] = m_data[j];
m_data[j] = x;
sort_sw = 1;
}
if (j + 1 < sort_cnt)
{
i++;
goto loop_2;
}
if (sort_sw == 1 || sort_gap > 1)
goto loop_1;
loop_e:
return;
}
【実行時間】(Pentium-75MHz VisualC++5.0 Release Mode)
件数 乱順 正順 逆順
CombSort(r) 1000 0.00000 0.00000 0.00000
CombSort(r) 10000 0.05000 0.05000 0.06000
CombSort(r) 30000 0.22000 0.16000 0.17000
CombSort(r) 100000 0.99000 0.66000 0.77000
CombSort(r) 300000 3.68000 2.36000 2.64000
CombSort(r) 1000000 13.84000 8.84000 9.67000
CombSort(r) 3000000 44.11000 29.55000 31.58000
残念ながらこの手の試験では実力が出ないのだが、オリジナルのCombSort
に比べて実際の生データを処理させる場合、１〜２割高速になる雰囲気が
ある。