デモの動かし方
横棒が積み重なっているグラフをクリックすると、整列が
始まります。同時に走らせて、実行速度の違いを体感しましょう。
デモを繰り返す場合は、ブラウザの｢更新」または「再読み込み」機能を利用して下さい。
整列がおわったグラフを再度クリックしてみるのも面白いでしょう。バブルソートは
すぐ終了する一方、クイックソートは、ちょっと手間取りますね。
このデモ自体のソース・プログラムを読むのもよいと思いますが、 以下アルゴリズムの紹介をします。
整数型の配列 ｖｄａｔａ の先頭からデータが格納されていて、 データの個数は整数型の変数 ｎｕｍ に入っているとします。 しつこく言いますが、vdata[0] から vdata[num-1] にデータが入っています。
＜アルゴリズム＞
- 変数ｖｔｏを定義し、初期値を ｎｕｍ にする
- 変数ｉ を定義し、初期値を ０ にする
- ｖｄａｔａの ｉ番目とｉ＋１番目を比較する
- ｖｄａｔａの ｉ番目の方が、大きかったら ｉ番目とｉ＋１番目を入替える
- ｉの値を１増やす
- ｉの値が、ｖｔｏ−１ より小さければ、手順３．に戻る
- ｉの値が、ｖｔｏ−１ に等しければ、ｖｔｏを１減らす
- ｖｔｏが０ならば終り。そうでなければ、手順２．に戻る
＜プログラム作成のヒント＞
- 手順１．および、手順７．手順８．で外側のｆｏｒループができます
for ( int vto = num; vto>0; vto-- ) { 手順 ２． 〜 手順 ６． }- 手順 ２．および、手順５．手順６．で内側のｆｏｒループができます
for ( int i = 0; i＜vto-1; i++ ) { 手順３．と手順４． }- 手順３．と手順４．は次のようにひとつのｉｆ文になります
if( vdata[i]>vdata[i+1] ) { int temp = vdata[i]; vdata[i] = vdata[i+1]; vdata[i+1] = temp; }結局、どーなるかというと．．．
バブル・ソートの様子をアニメにしたものが、 これです。
バブル・ソートのアニメや、 jdkに添付されているデモ The Sorting Algorithm Demo (1.1)をみて気づかれたかもしれませんが、バブル・ソートでは 一回の入替えで、位置が１つ分しか改善されません。離れたデータを入替え、 入替の効率を改善しましょう。
整数型の配列 ｖｄａｔａ の先頭からデータが格納されていて、 データの個数は整数型の変数 ｎｕｍ に入っているとします。
クイック・ソートのアプローチは、簡単にいうと以下のとおりです。
- 真中あたりのデータを一つ選び、このデータの値（Ｍとする）より小さいデータを左側に、 大きいデータを右側に集めます。
- 具体的には、左側から順にＭより大きいデータをさがし、 右側から順にＭより小さいデータをさがして入れ替えます。
- すべて入替え終わると、Ｍより小さいデータが左側に、Ｍより大きいデータが右側に 集まっているので、それぞれの部分について、同様の操作をほどこします。
＜アルゴリズム＞
- 変数 from と too をそれぞれ整列すべきデータの左端、右端とする
すなわち、初期値は from = 0; too = num-1;- M = vdata[ (from + too) / 2 ];
- int left = from;
int right = too;- (left <= right) である間、以下の手順７．までを繰り返す
left <= right であれば、vdata[left] と vdata[right] を入替え、 left++; right--; とする- right < left になった時、M より小さい値は、from から right の 間に、M より大きな値は、 left から too の間に移動している。 したがって、
vdata の from から right の間にデータがあれば整列し、さらに
vdata の left から too の間にデータがあれば整列する。クイック・ソートの様子をアニメにしたものが、 これです。
データのキーどうしの比較を行なわずに整列することができます。
たとえば、１０進３桁で表現されている次のようなデータがあるとします。データ
１２３ ２２１ ０１３ ２２０ ２１４ ３２２ ３０２ １１０ ０３２ まず、１の位に注目して、０から９までに振り分けます。
１の位が０ １の位が１ １の位が２ １の位が３ １の位が４ １の位が５... ２２０ ２２１ ３２２ １２３ ２１４ １１０ ３０２ ０１３ ０３２ 振り分けた結果を、１の位が０のものから順に、１列にまとめます。
次に、１０の位に注目して、同じように０から９に振り分けます。この時、順序を崩さないよう注意して下さい。
２２０ １１０ ２２１ ３２２ ３０２ ０３２ １２３ ０１３ ２１４
１０の位が０ １０の位が１ １０の位が２ １０の位が３ １０の位が４ １０の位が５... ３０２ １１０ ２２０ ０３２ ０１３ ２２１ ２１４ ３２２ １２３ 同じように、順序を崩さないように、１列にまとめます。
同じ手順を、１００の位について行えば、全体の整列が完了です。
３０２ １１０ ０１３ ２１４ ２２０ ２２１ ３２２ １２３ ０３２
０ １ ２ ３ ４ ５... ０１３ １１０ ２１４ ３０２ ０３２ １２３ ２２０ ３２２ ２２１
０１３ ０３２ １１０ １２３ ２１４ ２２０ ２２１ ３０２ ３２２