コックテールソート

　コックテールソート（cockail sort）は、シェーカーソート（shaker sort）とも呼ばれます。日本語版の Wikipedia では、シェーカーソートと呼んでいるようです。

　順方向のスキャンをやったら、引き続いて逆方向のスキャンを行います。これは、L1 キャッシュにデータが残されている段階で反転した処理を開始するために、キャッシュの恩恵に預れるという利点もありますし、実際にはソート対象範囲を更に絞りこむ工夫がされています。なかなか上手なことを考え出す人がいると、感心するばかりです。開発当時はキャッシュは無かったと思いますが。

　実行速度は、データの中身によって大きく左右されますが、バブルソートの 60% くらいの時間で処理が完了することもあります。結構頑張っています。

　バブルソートに比べれば速いといっても、とても実用的な速度ではないため、実測値の掲載は省略します。

特　徴

• 　バブルソートに比べれば、そこそこ速く動作します。
• 　無駄な動作をなくす工夫をする、お勉強の材料にはなるかもしれません。このような努力の積み重ねは大切なことです。

　ソースリストを掲載しますが、コピー & ペーストだと、インデントが壊れて汚くなっています。もう少しきれいなソースリストも用意しました。速度測定プログラムでのソースリストなので、処理を中断する Abort 処理が混じっていますから、削除してしまえばちょっとだけ処理速度が速くなります。スワップ処理に XMM レジスターを使うことで、ソート本体のレジスタ変数を少しでも確保して高速化する狙いがあります。

CocktailSort.txt　stdafx.txt

Type A

static DWORD __stdcall CocktailSortAR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort) { size_t sztFinalSwap, sztPtr; do { for( sztFinalSwap = sztPtr = pTop; sztPtr < pBtm; sztPtr++ ) { if( pArray[ sztPtr + 1 ].Key < pArray[ sztPtr ].Key ) { SwapUU( &pArray[ sztPtr + 1 ], &pArray[ sztPtr ] ); sztFinalSwap = sztPtr; } } pBtm = sztFinalSwap; if( pTop >= pBtm ) break; // for( sztFinalSwap = sztPtr = pBtm; sztPtr > pTop; sztPtr-- ) { if( pArray[ sztPtr - 1 ].Key > pArray[ sztPtr ].Key ) { SwapUU( &pArray[ sztPtr - 1 ], &pArray[ sztPtr ] ); sztFinalSwap = sztPtr; } } pTop = sztFinalSwap; if( *pAbort ) return 1223; } while( pTop < pBtm ); return 0; } DWORD __stdcall CocktailSortA(SortRecStruct* pArray, size_t pRecCount, bool* pAbort) { return CocktailSortAR( pArray, 0, pRecCount - 1, pAbort ); }

• 　配列型の記述形式です。

Type B

static DWORD __stdcall CocktailSortBR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort) { SortRecStruct *RecFinalSwap, *RecPtr; do { for( RecFinalSwap = RecPtr = pTop; RecPtr < pBtm; RecPtr++ ) { if( ( RecPtr + 1 )->Key < RecPtr->Key ) { SwapUU( RecPtr + 1, RecPtr ); RecFinalSwap = RecPtr; } } pBtm = RecFinalSwap; if( pTop >= pBtm ) break; // for( RecFinalSwap = RecPtr = pBtm; RecPtr > pTop; RecPtr-- ) { if( ( RecPtr - 1 )->Key > RecPtr->Key ) { SwapUU( RecPtr - 1, RecPtr ); RecFinalSwap = RecPtr; } } pTop = RecFinalSwap; if( *pAbort ) return 1223; } while( pTop < pBtm ); return 0; } DWORD __stdcall CocktailSortB(SortRecStruct* pArray, size_t pRecCount, bool* pAbort) { return CocktailSortBR( pArray, &pArray[ pRecCount - 1 ], pAbort ); }

• 　ポインタ型の記述形式です。

　ありがちなＣコンパイラでは、Type B のほうが高速になります。あなたのコンパイラではどうなるでしょうか。

注意事項

　シンプルなバブルソートに比べると、変数の数が多くなっています。win32 環境では、すべての変数が上手にレジスタ変数に展開されるか、あるいはメモリ内のローカル変数が発生するかどうかが処理速度の分かれ道にもなります。これは、コンパイラの最適化処理がどのような展開にするかに依存しますから、もしかすると、コンパイラを交換するだけで処理速度に影響が出るかもしれません。

　x64 環境では、使えるレジスタの数が多いので、この程度であればすべてレジスタ変数に収まりますから、この現象は起きにくいと考えられます。

　このサイトの冒頭でも記事にしていますが、比較の順序を左右逆にすると処理速度が速くなることもあります。いろいろなパターンのうち、どの方法が最良なのかはそれぞれの環境で異なります。