Small fast sort

単純かつ高速な Sortアルゴリズム

　手間をかけず高速な Sort Routineが必要な時、STLの sort()は便利ですが、
　　(1) QuickSort系の再帰アルゴリズムなので stack overflowが心配
　　(2) Code sizeが結構でかい
といった不満点もあります。

　そこで QuickSort並みに高速でかつ単純な CombSortアルゴリズムを紹介します。STL styleの template functionにしてみましたので STLの sort()同様、配列／vector container等の Sortに使うことが出来ます。

combsort.hqx

　良く使われる単純な SelectionSortも含めて 10000個の doubleを Sortしてみました。

#include    <iostream>
#include    <algorithm>
 
#include    "CElapsedTime.h"
#include    "CombSort.h"
#include    "SelectionSort.h"
 
const   long    NDATA = 10000;
double          data[NDATA];
 
void    main()
{
CElapsedTime    t;  // msec単位で経過時間を得る class
 
    for ( long i = 0; i < NDATA; i++ )  data[i] = rand() * 12.3;
    t.Get();
    sort(data,data + NDATA);    // STL sort()
    cout << "QuickSort:" << t.Get() << " msec" << endl;
 
    for ( long i = 0; i < NDATA; i++ )  data[i] = rand() * 12.3;
    t.Get();
    CombSort(data,data + NDATA);
    cout << "CombSort:" << t.Get() << " msec" << endl;
 
    for ( long i = 0; i < NDATA; i++ )  data[i] = rand() * 12.3;
    t.Get();
    SelectionSort(data,data + NDATA);
    cout << "SelectionSort:" << t.Get() << " msec" << endl;
}

　PowerMac8100/80での実行結果です。

QuickSort:36 msec CombSort:65 msec SelectionSort:7881 msec

　CombSortは単純なアルゴリズムにもかかわらず、SelectionSortの 100倍以上高速で QuickSortに迫る速度を発揮します。

この Pageは MacOS X + Radio UserLand で作っています。