個人的には、Dual Selection と呼んでいたのですが、英語版 Wikipedia に合わせました。
ミンマックスソート（Min Max sort）は、セレクションソートが最小値か最大値のどちらか一方でスキャンするのに対し、どうせなら１回のスキャンで最小値も最大値も両方処理するという、欲張りな考え方です。１度で２度おいしいという表現もできます。発想としては、それほどおかしな発想ではないのですが。
ただ、日本でも海外でも、昔から伝わる「おとぎ話」などでは、安易に欲を出さないように道徳教育をしていますよね…「お前が落としたのは、この金のオノか？ それともこちらの銀のオノか？」「私が落としたのは、両方でございます。」
１回のスキャン当たり成果物が２倍になったと言えば、画期的です。実際、10 件のソートをするときに最初の１回が終われば残りは８件に減るわけですから聞こえは良いです。しかし、10 万件のレコード数があると、２倍になったとはいえ、１回のスキャンでたったの２個しか成果物がないわけですから、やっぱり、もの悲しさを感じます。
展開されたアセンブルリストと比較しやすいように、for 文は使わず、do - while ループを使ってソースを作成しています。
このソートも CMOV 命令の影響を大きく受けます。セレクションショートの記事をまだご覧になっていない方は、事前にセレクションソートの記事をお読みください。
win32 環境での実行速度の例です。レコード数は 10 万件、数値の単位はミリ秒です。セレクションソートの Random32 の最小は３秒台でした。
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer Type A(VC) 4617.63 4633.23 4633.23 4648.83 4570.83 4461.63 4602.03 4586.43 Type B(VC) 5288.43 5304.03 5304.03 5288.43 5288.43 5304.03 5288.43 5304.03 Type C(VC) 2293.21 2262.01 2246.41 2293.21 2277.61 2277.61 2293.21 2293.21
同様に、x64 環境での実行速度の例を掲載します。レコード長が 16 バイトになるので、 win32 より少し時間がかかります。セレクションソートの Random32 の最小は３秒台でした。
Random32 Random32R Random15 Random15R Forward Reverse Constant Med Killer Type A(VC) 2808.02 2761.22 2839.22 2761.22 2761.22 2886.02 2823.62 2776.82 Type B(VC) 5226.03 5350.83 5350.83 5319.63 5350.83 5335.23 5335.23 5226.03 Type C(VC) 2262.01 2308.81 2293.21 2308.81 2293.21 2293.21 2308.81 2355.62
ソースリストを掲載しますが、コピー & ペーストだと、インデントが壊れて汚くなっています。もう少しきれいなソースリストも用意しました。速度測定プログラムでのソースリストなので、処理を中断する Abort 処理が混じっていますから、削除してしまえばちょっとだけ処理速度が速くなります。スワップ処理に XMM レジスターを使うことで、ソート本体のレジスタ変数を少しでも確保して高速化する狙いがあります。
static int __stdcall MinMaxSortAR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{
size_t sztMaxPtr, sztMinPtr, sztScan;
while( pTop < pBtm )
{
sztMinPtr = sztMaxPtr = pBtm; sztScan = pTop;
do
{
if( pArray[ sztScan ].Key > pArray[ sztMaxPtr ].Key )
sztMaxPtr = sztScan;
if( pArray[ sztScan ].Key < pArray[ sztMinPtr ].Key )
sztMinPtr = sztScan;
sztScan++;
}
while( sztScan < pBtm );
SwapUU( &pArray[ sztMaxPtr ], &pArray[ pBtm ] );
if( sztMinPtr == pBtm )
sztMinPtr = sztMaxPtr;
pBtm--;
SwapUU( &pArray[ sztMinPtr ], &pArray[ pTop++ ] );
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall MinMaxSortA(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return MinMaxSortAR( pArray, 0, pRecCount - 1, pAbort );
}
static DWORD __stdcall MinMaxSortBR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
SortRecStruct *RecMaxPtr, *RecMinPtr, *RecScan;
while( pTop < pBtm )
{
RecMinPtr = RecMaxPtr = pBtm; RecScan = pTop;
do
{
if( RecScan->Key > RecMaxPtr->Key )
RecMaxPtr = RecScan;
if( RecScan->Key < RecMinPtr->Key )
RecMinPtr = RecScan;
RecScan++;
}
while( RecScan < pBtm );
SwapUU( RecMaxPtr, pBtm );
if( RecMinPtr == pBtm )
RecMinPtr = RecMaxPtr;
pBtm--;
SwapUU( RecMinPtr, pTop++ );
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall MinMaxSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return MinMaxSortBR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}
static DWORD __stdcall MinMaxSortCR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{
SortRecStruct *RecMaxPtr, *RecMinPtr, *RecScan;
DWORD MaxKeyData, MinKeyData;
while( pTop < pBtm )
{
MinKeyData = MaxKeyData = pBtm->Key; RecMinPtr = RecMaxPtr = pBtm; RecScan = pTop;
do
{
if( RecScan->Key > MaxKeyData )
{
MaxKeyData = RecScan->Key; RecMaxPtr = RecScan;
}
if( RecScan->Key < MinKeyData )
{
MinKeyData = RecScan->Key; RecMinPtr = RecScan;
}
RecScan++;
}
while( RecScan < pBtm );
SwapUU( RecMaxPtr, pBtm );
if( RecMinPtr == pBtm )
RecMinPtr = RecMaxPtr;
pBtm--;
SwapUU( RecMinPtr, pTop++ );
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall MinMaxSortC(SortRecStruct* pArray, size_t pRecCount, bool* pAbort)
{
return MinMaxSortCR( pArray, &pArray[ pRecCount - 1 ], pAbort );
}
基本的にセレクションソートと同一ですので、ソースリストの他のバリエーションは省略します。いろいろなパターンを試して調べてようやく速く動くパターンが探し出せました。労力と成果のバランスが悪いです。
セレクションソートを参照してください。
← Selection Sort ｜ Insertion 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 |