バブルソートとクイックソート

MacBook Air 11" Mid 2013のVirtualBoxに導入してあるUbuntuを、14.04LTSから16.04LTSに更新した。
Ubuntuではほとんど開発しないが、CUIで開発するのには一番手軽な環境だ。
GCCの動作確認の"Hello World"がてら、バブルソートを実装した。
バブルソートは簡単で、配列の頭から順番に近傍の2つを比較して並べ直していくだけだ。
3 4 5 2 1をスタートとすると、
[3 4] 5 2 1 (3と4を比較する、すでに昇順なのでひっくり返さない)
3 [4 5] 2 1 (4と5を比較する、すでに昇順なのでひっくり返さない)
3 4 [5 2] 1 (5と2を比較して、ひっくり返す)
3 4 2 [5 1] (5と1を比較して、ひっくり返す)
3 4 2 1 5
これを頭からN-1番目まで、頭からN-2番目まで・・・頭までと繰り返していけばソートが完了する、こんな感じだ。
3 4 5 2 1
3 4 2 1 5
3 2 1 4 5
2 1 3 4 5
1 2 3 4 5
昇順でソートすると大きな数字が配列内を頭からお尻へ向かって上がっていく様が、まるで水中のあぶくが上がっていくように見えるのがバブルソートと言われる所以だ。

バブルソートは遅い。
そこでクイックソートを実装しようとしたが・・・忘れた。
慌ててアルゴリズムたいそうの教科書を開いて、復習だ。

プログラミングの宝箱 アルゴリズムとデータ構造 (C magazine)

まず暫定的な比較基準を決める

例えば3 4 5 2 1という配列がある場合、先頭の3を基準にする
(3) 4 5 2 1

配列を前後から同時にスキャンし、より前方にあり基準より大きい要素と、より後方にあり基準より小さい要素ペアを見つける

4と1がペアーになる

このペアをひっくり返す

(3) 1 5 2 4

これを繰り返し、基準より小さい要素は配列の前方に、基準より大きい要素は配列の後方に移動する

次は5と2がペアーになるので、これをひっくり返す
(3) 1 2 5 4

最後に基準より小さく、一番後方にある要素と基準をひっくり返す

2 1 (3) 5 4
これで基準(3)より小さい数は基準より前方に、大きい数は後方に移動される

あとは基準の前後の配列について、それぞれ同様の作業を各配列の要素数が1個になるまで繰り返す(再帰を利用する)

[2 1] -> [1 2] -> [1]で終了
[5 4] -> [4 5] -> [4]で終了
これで最終結果が得られる。
1 2 3 4 5

要素数200で試したところ、クイックソートはバブルソートの1/3以下の時間で処理を完了した。

void quick_sort(int bottom, int top, int* array)
{
	int indexLower, indexUpper, divider, buffer;
	if (bottom >= top)
		return;
	else
	{
		divider = array[bottom];
		for (indexLower = bottom, indexUpper = top; indexLower < indexUpper;)
		{
			while (indexLower <= indexUpper && array[indexLower] <= divider)
				indexLower++;
			while (indexLower <= indexUpper && array[indexUpper] > divider)
				indexUpper--;
			if (indexLower < indexUpper)
			{
				buffer = array[indexLower];
				array[indexLower] = array[indexUpper];
				array[indexUpper] = buffer;

			}
		}
		buffer = array[bottom];
		array[bottom] = array[indexUpper];
		array[indexUpper] = buffer;
		//
		quick_sort(bottom, indexUpper - 1, array);
		quick_sort(indexUpper + 1, top, array);
	}
}