(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 に比べて実際の生データを処理させる場合、1〜2割高速になる雰囲気が ある。
←↑→
(C)copyright ffortune.net 1995-2016 produced by ffortune and Lumi.
お問い合わせはこちらから