コムソート（comb sort）は、バブルソートの仲間に入れられますが、最初のうちは隣どうしで比較とスワップをするのではなく、大きな間隔で行います。バブルソートだと、小さなものを先頭に集めるタイプの時、最後の方になってようやく最小値が出現すると、スワップを何回も繰り返しながら、はるばると先頭まで移動していくことになります。しかし、間隔を大きくしてあげれば、１回のスワップで大きく移動できますから、効率が飛躍的に向上するケースが出てきます。
逆に、大きな移動量を必要としない、レコード数が十分に少ないときは、条件判定する if 文の実行回数が増えているために、あまり速くなりません。適度なレコード数以上の時に、大きな効果を発揮します。
win32 環境での速度例です。レコード数 ５千万件、レコード長８バイト、数値の単位はミリ秒です。
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer Type A(VC) 10966.87 10935.67 8065.25 8174.45 3978.03 4492.83 3978.03 4633.23 Type B(VC) 10686.07 10639.27 7628.45 7628.45 3354.02 3790.82 3229.22 3993.63
x64 環境での速度例です。レコード数 ５千万件、レコード長 16 バイト、数値の単位はミリ秒です。
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer Type A(VC) 11356.87 11466.07 8954.46 9048.06 5943.64 6380.44 5974.84 6817.24 Type B(VC) 11824.88 11559.67 8829.66 8845.26 4882.83 5444.43 4882.83 5803.24
ソースリストを掲載しますが、コピー & ペーストだと、インデントが壊れて汚くなっています。もう少しきれいなソースリストも用意しました。速度測定プログラムでのソースリストなので、処理を中断する Abort 処理が混じっていますから、削除してしまえばちょっとだけ処理速度が速くなります。スワップ処理に XMM レジスターを使うことで、ソート本体のレジスタ変数を少しでも確保して高速化する狙いがあります。
static DWORD __stdcall CombSortAR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
SortRecStruct *NewTbl;
size_t sztPtr, sztCount, sztGap, sztChkPtr;
bool bNeedRefresh = false;
NewTbl = &pArray[ pTop ]; sztCount = sztGap = pBtm - pTop + 1;
while( ( sztGap > 1 ) || bNeedRefresh )
{
if( sztGap > 1 )
{
sztGap = ( size_t ) ( ( double ) sztGap / 1.247330950103979 );
}
bNeedRefresh = false; sztChkPtr = sztGap;
for( sztPtr = 0; sztChkPtr < sztCount; sztChkPtr++, sztPtr++ )
{
if( NewTbl[ sztPtr ].Key > NewTbl[ sztChkPtr ].Key )
{
SwapUU( &NewTbl[ sztPtr ], &NewTbl[ sztChkPtr ] );
bNeedRefresh = true;
}
}
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall CombSortA(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return CombSortAR( pArray, 0, pRecCount - 1, pAbort );
}
static DWORD __stdcall CombSortBR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
SortRecStruct *NewTbl;
size_t sztPtr, sztCount, sztGap, sztChkPtr;
bool bNeedRefresh = false;
NewTbl = &pArray[ pTop ]; sztCount = sztGap = pBtm - pTop + 1;
while( ( sztGap > 1 ) || bNeedRefresh )
{
if( sztGap > 1 )
{
//sztGap = ( size_t ) ( ( double ) sztGap / 1.247330950103979 );
sztGap = sztGap * 10 / 13;
}
bNeedRefresh = false; sztChkPtr = sztGap;
for( sztPtr = 0; sztChkPtr < sztCount; sztChkPtr++, sztPtr++ )
{
if( NewTbl[ sztPtr ].Key > NewTbl[ sztChkPtr ].Key )
{
SwapUU( &NewTbl[ sztPtr ], &NewTbl[ sztChkPtr ] );
bNeedRefresh = true;
}
}
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall CombSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return CombSortBR( pArray, 0, pRecCount - 1, pAbort );
}
static DWORD __stdcall CombSortCR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
SortRecStruct *NewTbl;
size_t sztPtr, sztCount, sztGap, sztChkPtr;
bool bNeedRefresh = false;
NewTbl = &pArray[ pTop ]; sztCount = sztGap = pBtm - pTop + 1;
while( ( sztGap > 1 ) || bNeedRefresh )
{
if( sztGap > 1 )
{
//sztGap = ( size_t ) ( ( double ) sztGap / 1.247330950103979 );
sztGap = sztGap * 10 / 13;
if( sztGap == 9 && sztGap == 10 )
sztGap = 11;
}
bNeedRefresh = false; sztChkPtr = sztGap;
for( sztPtr = 0; sztChkPtr < sztCount; sztChkPtr++, sztPtr++ )
{
if( NewTbl[ sztPtr ].Key > NewTbl[ sztChkPtr ].Key )
{
SwapUU( &NewTbl[ sztPtr ], &NewTbl[ sztChkPtr ] );
bNeedRefresh = true;
}
}
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall CombSortC(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return CombSortCR( pArray, 0, pRecCount - 1, pAbort );
}
アセンブラレベルで最初から記述した場合は、アドレス計算がもう少し高速に行えるので、もう少し速く実行できます。しかし、毎回アセンブラのソースを作るのは大変なのですから、このあたりで我慢するしかありません。
たまたまですが、このソート法は、スーパースケーラーでの同時並行動作が行いにくいタイプの演算になってしまいます。
← Heap Sort ｜ Merge Sort →
| contents |
| Top Page caution Bubble Sort Odd Even Sort Cocktail Sort Gnome Sort Selection Sort Min Max Sort Insertion Sort Shell Sort Heap Sort Comb Sort Merge Sort Quick Sort Do-Re-Mi-Fa Sort chat |