デモの動かし方
横棒が積み重なっているグラフをクリックすると、整列が
始まります。同時に走らせて、実行速度の違いを体感しましょう。
デモを繰り返す場合は、ブラウザの「更新」または「再読み込み」機能を利用して下さい。
整列がおわったグラフを再度クリックしてみるのも面白いでしょう。バブルソートは
すぐ終了する一方、クイックソートは、ちょっと手間取りますね。
このデモ自体のソース・プログラムを読むのもよいと思いますが、 以下アルゴリズムの紹介をします。
整数型の配列 vdata の先頭からデータが格納されていて、 データの個数は整数型の変数 num に入っているとします。 しつこく言いますが、vdata[0] から vdata[num-1] にデータが入っています。
<アルゴリズム>
- 変数vtoを定義し、初期値を num にする
- 変数i を定義し、初期値を 0 にする
- vdataの i番目とi+1番目を比較する
- vdataの i番目の方が、大きかったら i番目とi+1番目を入替える
- iの値を1増やす
- iの値が、vto−1 より小さければ、手順3.に戻る
- iの値が、vto−1 に等しければ、vtoを1減らす
- vtoが0ならば終り。そうでなければ、手順2.に戻る
<プログラム作成のヒント>
- 手順1.および、手順7.手順8.で外側のforループができます
for ( int vto = num; vto>0; vto-- ) { 手順 2. 〜 手順 6. }- 手順 2.および、手順5.手順6.で内側のforループができます
for ( int i = 0; i<vto-1; i++ ) { 手順3.と手順4. }- 手順3.と手順4.は次のようにひとつのif文になります
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)をみて気づかれたかもしれませんが、バブル・ソートでは 一回の入替えで、位置が1つ分しか改善されません。離れたデータを入替え、 入替の効率を改善しましょう。
整数型の配列 vdata の先頭からデータが格納されていて、 データの個数は整数型の変数 num に入っているとします。
クイック・ソートのアプローチは、簡単にいうと以下のとおりです。
- 真中あたりのデータを一つ選び、このデータの値(Mとする)より小さいデータを左側に、 大きいデータを右側に集めます。
- 具体的には、左側から順にMより大きいデータをさがし、 右側から順にMより小さいデータをさがして入れ替えます。
- すべて入替え終わると、Mより小さいデータが左側に、Mより大きいデータが右側に 集まっているので、それぞれの部分について、同様の操作をほどこします。
<アルゴリズム>
- 変数 from と too をそれぞれ整列すべきデータの左端、右端とする
すなわち、初期値は from = 0; too = num-1;- M = vdata[ (from + too) / 2 ];
- int left = from;
int right = too;- (left <= right) である間、以下の手順7.までを繰り返す
while( left < too かつ vdata[left] < M ) left++; while( from < right かつ M < vdata[right] ) right--; left <= right であれば、vdata[left] と vdata[right] を入替え、 left++; right--; とする- right < left になった時、M より小さい値は、from から right の 間に、M より大きな値は、 left から too の間に移動している。 したがって、
vdata の from から right の間にデータがあれば整列し、さらに
vdata の left から too の間にデータがあれば整列する。クイック・ソートの様子をアニメにしたものが、 これです。
データのキーどうしの比較を行なわずに整列することができます。
たとえば、10進3桁で表現されている次のようなデータがあるとします。データ
123 221 013 220 214 322 302 110 032 まず、1の位に注目して、0から9までに振り分けます。
1の位が0 1の位が1 1の位が2 1の位が3 1の位が4 1の位が5... 220 221 322 123 214 110 302 013 032 振り分けた結果を、1の位が0のものから順に、1列にまとめます。
次に、10の位に注目して、同じように0から9に振り分けます。この時、順序を崩さないよう注意して下さい。
220 110 221 322 302 032 123 013 214
10の位が0 10の位が1 10の位が2 10の位が3 10の位が4 10の位が5... 302 110 220 032 013 221 214 322 123 同じように、順序を崩さないように、1列にまとめます。
同じ手順を、100の位について行えば、全体の整列が完了です。
302 110 013 214 220 221 322 123 032
0 1 2 3 4 5... 013 110 214 302 032 123 220 322 221
013 032 110 123 214 220 221 302 322