インサーションソート（insertion sort）は、比較と交換の処理をするに当たり、「もうこの先はソート済み」という部分を検出すると、それ以上深追いしないという特徴を持っています。
win32 環境での速度例です。レコード数 10 万件、レコード長８バイト、数値の単位はミリ秒です。ちなみにバブルソートの Random32 は 15 秒台です。
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer Type A(VC) 3135.62 3120.02 3151.22 3166.82 0.00 6271.24 0.00 3135.62 Type B(VC) 3135.62 3120.02 3151.22 3166.82 0.00 6224.44 0.00 3120.02 Type C(VC) 1825.21 1887.61 1825.21 1872.01 0.00 3837.62 0.00 1903.21 Type D(VC) 1809.61 1856.41 1825.21 1856.41 0.00 3759.62 0.00 1778.41
x64 環境での速度例です。レコード数 10 万件、レコード長 16 バイト、数値の単位はミリ秒です。ちなみにバブルソートの Random32 は 16 秒台です。
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer Type A(VC) 3884.42 3946.83 3900.03 3915.63 0.00 7878.05 0.00 3931.23 Type B(VC) 3853.22 3900.03 3868.82 3884.42 0.00 7815.65 0.00 3853.22 Type C(VC) 2901.62 2995.22 2979.62 2979.62 0.00 5974.84 0.00 2964.02 Type D(VC) 2901.62 2979.62 2964.02 2932.82 0.00 5928.04 0.00 2948.42
ソースリストを掲載しますが、コピー & ペーストだと、インデントが壊れて汚くなっています。もう少しきれいなソースリストも用意しました。速度測定プログラムでのソースリストなので、処理を中断する Abort 処理が混じっていますから、削除してしまえばちょっとだけ処理速度が速くなります。スワップ処理やコピー処理に XMM レジスターを使うことで、ソート本体のレジスタ変数を少しでも確保して高速化する狙いがあります。
static DWORD __stdcall InsertionSortAP(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
SortRecStruct *ScanPtr, *CopyPtr;
ScanPtr = pTop + 1;
while( ScanPtr <= pBtm )
{
CopyPtr = ScanPtr;
while( ( CopyPtr > pTop ) && ( CopyPtr - 1 )->Key > CopyPtr->Key )
{
SwapUU( CopyPtr, CopyPtr - 1 ); CopyPtr--;
}
if( *pAbort ) return 1223;
ScanPtr++;
}
return 0;
}
DWORD __stdcall InsertionSortA(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
DWORD dwResult = 0;
if( pRecCount > 1 )
dwResult = InsertionSortAP( pArray, &pArray[ pRecCount - 1 ], pAbort );
return dwResult;
}
static DWORD __stdcall InsertionSortBP(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
SortRecStruct *ScanPtr, *CopyPtr;
ScanPtr = pBtm - 1;
while( ScanPtr >= pTop )
{
CopyPtr = ScanPtr;
while( ( CopyPtr < pBtm ) && ( CopyPtr + 1 )->Key < CopyPtr->Key )
{
SwapUU( CopyPtr, CopyPtr + 1 ); CopyPtr++;
}
if( *pAbort ) return 1223;
ScanPtr--;
}
return 0;
}
DWORD __stdcall InsertionSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
DWORD dwResult = 0;
if( pRecCount > 1 )
dwResult = InsertionSortBP( pArray, &pArray[ pRecCount - 1 ], pAbort );
return dwResult;
}
static DWORD __stdcall InsertionSortCP(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
SortRecStruct TempData;
SortRecStruct *ScanPtr, *CopyPtr;
ScanPtr = pTop + 1;
while( ScanPtr <= pBtm )
{
if( ( ScanPtr - 1 )->Key > ScanPtr->Key )
{
CopyRec( &TempData, ScanPtr ); CopyPtr = ScanPtr;
do
{
CopyRec( CopyPtr, CopyPtr - 1 ); CopyPtr--;
}
while( ( CopyPtr > pTop ) && ( ( CopyPtr - 1 )->Key > TempData.Key ) );
CopyRec( CopyPtr, &TempData );
if( *pAbort ) return 1223;
}
ScanPtr++;
}
return 0;
}
DWORD __stdcall InsertionSortC(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
DWORD dwResult = 0;
if( pRecCount > 1 )
dwResult = InsertionSortCP( pArray, &pArray[ pRecCount - 1 ], pAbort );
return dwResult;
}
static DWORD __stdcall InsertionSortDP(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
SortRecStruct TempData;
SortRecStruct *ScanPtr, *CopyPtr;
ScanPtr = pBtm - 1;
while( ScanPtr >= pTop )
{
if( ( ScanPtr + 1 )->Key < ScanPtr->Key )
{
CopyRec( &TempData, ScanPtr ); CopyPtr = ScanPtr;
do
{
CopyRec( CopyPtr, CopyPtr + 1 ); CopyPtr++;
}
while( ( CopyPtr < pBtm ) && ( ( CopyPtr + 1 )->Key < TempData.Key ) );
CopyRec( CopyPtr, &TempData );
if( *pAbort ) return 1223;
}
ScanPtr--;
}
return 0;
}
DWORD __stdcall InsertionSortD(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
DWORD dwResult = 0;
if( pRecCount > 1 )
dwResult = InsertionSortDP( pArray, &pArray[ pRecCount - 1 ], pAbort );
return dwResult;
}
レコード数が多いときはバイナリサーチを併用して、「どこまでの深さ」を速く特定する方法もある−という紹介記事もありますが、レコード数が多いときは他のソート法に切り替える方が簡単です。せっかく短いリストで、少ないレジスタ変数のものを、わざわざ複雑にして残りの処理の低速化を招く必要はありません。
場合によっては、ちまちまとコピーを繰り返すよりも、memcpy など、まとめて転送できる方法を使うともう少し速くなるケースもあります。
ソースリストの行数が短くなるからといって、安易にスワップ型のリストを掲載しているようなサイトの記事は、データの動きを正確に把握しているとはとても思えませんから、全く信用できません。
個人的には、Type-C のソースが最も使いやすく感じます。クイックソートのレコードが少なくなってきたときには、インサーションソートに切り替えると、より高速になるなど、使い勝手が良いです。
また、インサーションソート単体でも、事前にちょっとした工夫を加えると、実行速度が大幅に向上することがあります。
static void __stdcall DualSort(SortRecStruct* p1, SortRecStruct* p2)
{
if( p1->Key > p2->Key )
{
SwapSortRec( p1, p2 );
}
}
static void __stdcall TriSort(SortRecStruct* p1, SortRecStruct* p2, SortRecStruct* p3)
{
DualSort( p1, p2 ); DualSort( p2, p3 ); DualSort( p1, p2 );
}
static void __stdcall TriInsertionSortPA_VC(SortRecStruct* pTop, SortRecStruct* pBtm)
{
SortRecStruct TempData;
SortRecStruct *PtrL, *PtrM, *PtrR;
size_t sztSpan;
sztSpan = ( ( size_t ) ( pBtm - pTop ) + 1 ) / 2;
while( sztSpan >= 3 )
{
PtrL = pTop; PtrR = PtrL + sztSpan;
PtrM = PtrL + ( ( PtrR - pTop ) + 1 ) / 2;
while( PtrR <= pBtm )
{
TriSort( PtrL, PtrM, PtrR );
PtrL++; PtrM++; PtrR++;
}
sztSpan /= 2;
}
// Insertion Sort
PtrL = pTop + 1;
while( PtrL <= pBtm )
{
if( ( PtrL - 1 )->Key > PtrL->Key )
{
CopySortRec( &TempData, PtrL ); PtrR = PtrL;
do
{
CopySortRec( PtrR, PtrR - 1 ); PtrR--;
}
while( ( PtrR > pTop ) && ( ( PtrR - 1 )->Key > TempData.Key ) );
CopySortRec( PtrR, &TempData );
}
PtrL++;
}
}
この例では、事前に３か所の入れ替えの処理を入れていますが、インサーションソートで 1810ms かかっていたものが、94ms になり、19 倍ほど速度が向上します。
要するに、値の小さなものはできるだけ小さなアドレスに、大きなものは大きなアドレスに遠距離で飛ばすという簡単な下準備だけでも、かなり速くなるということです。実際、シェルソートやコムソートはこのような考え方を下準備ではなく、本体部分で実現しています。
← Min Max Sort ｜ Shell 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 |