※「セキュリティ保護のため...」というメッセージが出る方・日本語が入力できない方へ
(2)バブルソート

  王様探しのバリエーション。王様探しでは、１番目のデータと２番目のデ
  ータを比較したら、次には１番目と３番目、１番目と４番目、という比較
  の仕方をしていく。

　バブルの場合は、１番目と２番目、２番目と３番目、３番目と４番目、と
　いうふうに比較していく。すると大きなデータが泡となって浮かび上がる
　かのように後ろの方に集まっていく。そこで「バブル」の名前がある。

　これも遅いソートであり、実用性は全くない。しかし後述のコムソートの
　基礎になる。

【Coding Sample】(Bubble Sort Original)

void CSortDlg::BubbleSort()
{
	int i,j;
	long sort_cnt = m_dcnt;
	if (sort_cnt<=1)
		goto loop_e;

	//In one path, the biggest member goes to last
loop_1:
	for (i=0; i<sort_cnt-1; i++)
	{
		j=i+1;
		if (m_data[i]>m_data[j])
		{
			long k;
			k = m_data[i];
			m_data[i] = m_data[j];
			m_data[j] = k;
		}
	}
	sort_cnt--;
	if (sort_cnt>1)
		goto loop_1;
loop_e:
	return;
}

【実行時間】(Pentium-75MHz VisualC++5.0 Release Mode)

　　             件数　   乱順　　　　正順　　　　逆順
BubbleSort(r)     1000    0.11000     0.05000     0.06000
BubbleSort(r)    10000    6.81000     5.98000     8.57000
BubbleSort(r)    30000   90.19000    69.04000    90.13000

　オリジナルのバブルソートの場合も、元々のデータの並びには依存しない。


　さて、王様探しの場合はまともに必ずn(n-1)回の比較をせざるを得ないが、
　実はバブルソートの場合は、途中で一度も入れ替えが起きなかったら、そ
　れでもう処理終了としてよい。つまり運が良ければ、n(n-1)まで行かずに
　途中で終了してくれる可能性があり、その分、王様探しより若干速くなる。

　実は後述のコムソートというのは、この問題に着目し、その利点をうまく
　活用しているのである。この手法で上記ロジックを改良したのが次のもの
　である。

【Coding Sample】(Bubble Sort Revised)

void CSortDlg::BubbleSort2()
{
	int i,j,sort_sw;
	long sort_cnt = m_dcnt;
	if (sort_cnt<=1)
		goto loop_e;

	//In one path, the biggest member goes to last
loop_1:
	sort_sw = 0;
	for (i=0; i<sort_cnt-1; i++)
	{
		j=i+1;
		if (m_data[i]>m_data[j])
		{
			long k;
			k = m_data[i];
			m_data[i] = m_data[j];
			m_data[j] = k;
			sort_sw = 1;
		}
	}
	sort_cnt--;
	if (sort_cnt>1 && sort_sw==1)
		goto loop_1;
loop_e:
	return;
}


【実行時間】(Pentium-75MHz VisualC++5.0 Release Mode)

　　　             件数　   乱順　　　　正順　　　　逆順
BubbleSort2(r)     1000    0.06000     0.00000     0.05000
BubbleSort2(r)    10000    7.41000     0.00000     7.75000
BubbleSort2(r)    30000   71.08000     0.00000    74.53000

　原理から当然のこととして、予めある程度、並んでいるデータに対しては
　この方法はものすごく速い。

　しかしBubble Sortは更に改良することができる。つまり、どこかから先
　入れ替えが起きなかったとしたら、そこから先は全てもう並んでいると
　考えてよい。従って次はカウントを１減らすのではなく、最後に入れ替え
　が起きたところの番号にしてしまうのである。こうするとかなりの改良に
　なる。

【Coding Sample】(Bubble Sort More Revised)

void CSortDlg::BubbleSort3()
{
	int i,j,sort_sw;
	long sort_cnt = m_dcnt;
	if (sort_cnt<=1)
		goto loop_e;

	//In one path, the biggest member goes to last
loop_1:
	sort_sw = 0;
	for (i=0; i<sort_cnt-1; i++)
	{
		j=i+1;
		if (m_data[i]>m_data[j])
		{
			long k;
			k = m_data[i];
			m_data[i] = m_data[j];
			m_data[j] = k;
			sort_sw = j;
		}
	}
	sort_cnt = sort_sw;
	if (sort_cnt>1)
		goto loop_1;
loop_e:
	return;
}

【実行時間】(Pentium-75MHz VisualC++5.0 Release Mode)

　　　             件数　   乱順　　　　正順　　　　逆順
BubbleSort3(r)     1000    0.06000     0.00000     0.05000
BubbleSort3(r)    10000    7.25000     0.00000     7.58000
BubbleSort3(r)    30000   76.79000     0.00000    76.95000

　残念ながら乱順では First Revised より数字が悪くなってしまった。
　しかし「ある程度並んでいるデータ」に対しては、このSecond Revised
　の方がFirst Revisedより圧倒的に速いのである。