   
（１）考え方
隣り合う要素を比較し，
必要であれば交換する作業を繰り返して並び替えます。
この方法では，
値の小さいデータが交換のたびに上に動いてくるようにみえます。
ですから，泡が液体中を上にあがってくる様子にたとえて，
バブルソート（bubble sort), 泡立ちソート等と呼ばれます。
［プログラム例］
private void swap(ref int A,ref
int B)
{
int X=A; A=B; B=X;
}
private void バブルソート()
{
int i,j;
for(i = 0; i < Data.Length
-
1; i++)
for(j=Data.Length-1; j>i;
j--)
if(Data[j-1]>Data[j])
swap(ref Data[j-1], ref Data[j]);
}
（２）改良１
前例の4回目のパスを見ると，1回も交換されていません。
交換されていないということは，
すでに昇順に並んでいるということですから，
この時点で，作業を中止することができます。
したがって，次のようにプログラムを改良できます。
［プログラム例］
private void バブルソート改良版()
{
int i, j; bool notExchange;
for(i=0;i<Data.Length-1;i++)
{
notExchange=true;
for(j=Data.Length-1; j>i;
j--)
if(Data[j-1]>Data[j])
{
swap(ref Data[j-1], ref
Data[j]);
notExchange=false;
}
if(notExchange) break;
}
}
（３）改良２
次のような例を考えてみましょう。
この例の場合，最後に交換した位置より前は，
整列済みであることが分かりますから，
更に以下のように改良できます。
［プログラム例］
private void バブルソート改良版2()
{
int k=0;bool notExchange; n = Data.Length
- 1;
while (k < n - 1)
{
int j; int last n - 1； notExchange=true;
for(j= n -1; j>k; j--)
if(Data[j-1]>Data[j])
{
swap(ref Data[j-1], ref
Data[j]);
last = j;
notExchange=false;
}
if(notExchange) break;
k=last;
}
}
（４）その他
次のように，最大値が先頭にきているような例では，
改良１，改良２でも早期に打ち切ることはできません。
そこで，奇数パスでは，最小要素を先頭に移動，
偶数パスでは，最大要素を末尾に移動する方法もあります。
この方法は，
双方向バブルソート（bidirection bubble sort），
シェーカーソート（shaker sort）等と呼ばれます。
余裕のある方は，これまでのプログラム例を参考にして，
双方向バブルソートのプログラムを作成してみましょう。
 1. 基本的なアルゴリズム
2. 基本的なデータ構造
3. 操作を伴うデータ構造
4. 探索
5. 再帰的アルゴリズム
6. ソート
7. 集合
8. 文字列処理
9. 色々なアルゴリズム
上のタイトルをクリックします
|
6．2 単純交換法