バブルソート（bubble sort）は、隣どうしのデータの大小関係を比べる方法を、比較位置を１つずつ変えながら、ひたすら繰り返します。
速度が遅いので、実際の場面でこの技法が使われることはありませんが、転送回数が多いだけに、勉強のネタとして紹介されることが多いようです。隣どうしで交換と覚えていれば、その記憶を頼りにバブルソートを完成させることも簡単です。
展開されたアセンブルリストと比較しやすいように、for 文は使わず、do - while ループを使ってソースを作成しています。
もともと処理速度が遅くてとても実用的ではないため、実測値の掲載は省略します。
ソースリストを掲載しますが、コピー & ペーストだと、インデントが壊れて汚くなっています。もう少しきれいなソースリストも用意しました。速度測定プログラムでのソースリストなので、処理を中断する Abort 処理が混じっていますから、削除してしまえばちょっとだけ処理速度が速くなります。スワップ処理に XMM レジスターを使うことで、ソート本体のレジスタ変数を少しでも確保して高速化する狙いがあります。
static DWORD __stdcall BubbleSortAR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{ // reverse scan
size_t sztScanPtr;
while( pTop < pBtm )
{
sztScanPtr = pBtm;
do
{
if( pArray[ sztScanPtr - 1 ].Key > pArray[ sztScanPtr ].Key )
{
SwapUU( &pArray[ sztScanPtr - 1 ], &pArray[ sztScanPtr ] );
}
sztScanPtr--;
}
while( sztScanPtr > pTop );
pTop++;
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall BubbleSortA(SortRecStruct* pArray, size_t pRecordCount, bool* pAbort)
{
return BubbleSortAR( pArray, 0, pRecordCount - 1, pAbort );
}
static DWORD __stdcall BubbleSortBR(SortRecStruct* pArray, size_t pTop, size_t pBtm, bool* pAbort)
{ // forward scan
size_t sztScanPtr;
while( pTop < pBtm )
{
sztScanPtr = pTop;
do
{
if( pArray[ sztScanPtr + 1 ].Key < pArray[ sztScanPtr ].Key )
{
SwapUU( &pArray[ sztScanPtr + 1 ], &pArray[ sztScanPtr ] );
}
sztScanPtr++;
}
while( sztScanPtr < pBtm );
pBtm--;
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall BubbleSortB(SortRecStruct* pArray, size_t pRecordCount, bool* pAbort)
{
return BubbleSortBR( pArray, 0, pRecordCount - 1, pAbort );
}
static DWORD __stdcall BubbleSortCR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{ // reverse scan
SortRecStruct *RecScan;
while( pTop < pBtm )
{
RecScan = pBtm;
do
{
if( ( RecScan - 1 )->Key > RecScan->Key )
{
SwapUU( RecScan - 1, RecScan );
}
RecScan--;
}
while( RecScan > pTop );
pTop++;
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall BubbleSortC(SortRecStruct* pArray, size_t pRecordCount, bool* pAbort)
{
return BubbleSortCR( pArray, &pArray[ pRecordCount - 1 ], pAbort );
}
static DWORD __stdcall BubbleSortDR(SortRecStruct* pTop, SortRecStruct* pBtm, bool* pAbort)
{ // forward scan
SortRecStruct *RecScan;
while( pTop < pBtm )
{
RecScan = pTop;
do
{
if( ( RecScan + 1 )->Key < RecScan->Key )
{
SwapUU( RecScan + 1, RecScan );
}
RecScan++;
}
while( RecScan < pBtm );
pBtm--;
if( *pAbort ) return 1223;
}
return 0;
}
DWORD __stdcall BubbleSortD(SortRecStruct* pArray, size_t pRecordCount, bool* pAbort)
{
return BubbleSortDR( pArray, &pArray[ pRecordCount - 1 ], pAbort );
}
ところで、配列型の表記とポインタ型の表記の違いですが、多くのケースではポインタ型にすると高速コードを生成してくれる場合が多いですが、バブルソートの場合は筆者が使っているコンパイラでは逆に遅いコードを生成してくれます。希望する生成コードになかなかなってくれません。他のコンパイラや他のシステムでも、配列型とポインタ型では実行速度に差が出る可能性は十分あります。
ちなみに、バブルソート以外では、ポインタ型で表記するほうが、断然速くなります。
Ｃ言語ではなく、アセンブラでのみ専用設計としてコーディングする場合には、カウンタを使って比較命令をなくすことで実行速度が向上するケースもあります。外側ループの実行回数は pBtm - pTop の回数になります。内側ループの回数は、内側ループ開始直前の外側ループの値になります。例えば、外側ループのカウンタが３であれば、内側ループの回数は３回になります。スキャンポインタとカウンタを両方とも演算させるのは一見すると無駄ですが、実際にはスーパースケーラーによって同時並行動作しますから、CMP 命令を実行しない分だけ速くするケースもありうるということです。ただ、そのような高速化処理を行っても、バブルソートらしい遅さからは逃れられません。
このサイトの冒頭でも記事にしていますが、比較の順序を左右逆にすると処理速度が速くなることもあります。いろいろなパターンのうち、どの方法が最良なのかはそれぞれの環境で異なります。ただし、バブルソートとして速くなったところでバブルソートらしい遅さであることには変わりなく、速さを追求する目的の方は他の技法を迷わずに選択してください。
速さの違いをお勉強のために研究してみたい方は、上記４種類のソースリストで、左右の比較を取り換えたもの、つまり８種類のソースで実験してみてください。また、お友達に頼んで、別のプロセッサーで実験すると違う結果が出てくるかもしれません。その結果、スパースケーラの動作やキャッシュメモリへの展開方法を理解できるようになるかもしれません。
マイクロプロセッサーの理解を深めるには、セレクションソートの記事もあわせてお読みになると、少しだけ理解を深められるかもしれません。本当はご自分で回路設計をするのが最良ですが。
紹介記事によっては、スワップしたかどうかのフラグを変数として持っておき、内側ループが終了した時点でフラグの内容を確認し、一度もスワップされなかったらソート済みの状態なので処理を打ち切るというロジックを組み込んでいる例もあります。
そのようなデータが多い場合には、この最適化は有効ですが、フラグを設定したり、フラグをチェックする行為を高速ループの最中にちょくちょくと実行しているわけですから、その処理自身が速度低下の原因になることもあります。
特に、win32 環境では、自由に使える汎用レジスタが７個しかありませんから、安易に機能を追加したら、レジスタの数が足りなくなって余計に遅くなったということも起こるかもしれません。本に書いてあるから速いとか、インターネットでそう書いてあったから速いというものではありません。最適化をやったほうが良いのか、やめたほうが良いのかは実際に実験して見極めてください。
← caution ｜ Odd Even 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 |