第13章補足 ソートについて

【テーマ】
配列に記憶したデータを整列するためのアルゴリズムをいくつか紹介します。
プログラミングの初歩の問題としてよく取り上げられるのが、
です。 アルゴリズムが単純で解りやすいためでしょう。比較回数や、 入替回数を考えた場合、あまり効率のよいアルゴリズムではありませんが、データ 件数が少ない場合は、あまり気にすることはありません。
バブル・ソートにはいろいろな工夫が加えられています。
入替を行う方向を交互に変更すると、かなり早く整列される様子は、 jdkに添付されているデモ The Sorting Algorithm Demo (1.1)でよくわかります。

デモの動かし方
横棒が積み重なっているグラフをクリックすると、整列が 始まります。同時に走らせて、実行速度の違いを体感しましょう。
デモを繰り返す場合は、ブラウザの「更新」または「再読み込み」機能を利用して下さい。
整列がおわったグラフを再度クリックしてみるのも面白いでしょう。バブルソートは すぐ終了する一方、クイックソートは、ちょっと手間取りますね。

このデモ自体のソース・プログラムを読むのもよいと思いますが、 以下アルゴリズムの紹介をします。

【目次】
  1. バブル・ソート
  2. クイック・ソート
  3. ラディックス・ソート

ページの先頭へ

 13補.1 バブル・ソート

整数型の配列 vdata の先頭からデータが格納されていて、 データの個数は整数型の変数 num に入っているとします。 しつこく言いますが、vdata[0] から vdata[num-1] にデータが入っています。

<アルゴリズム>

  1. 変数vtoを定義し、初期値を num にする
  2. 変数i を定義し、初期値を 0 にする
  3. vdataの i番目とi+1番目を比較する
  4. vdataの i番目の方が、大きかったら i番目とi+1番目を入替える
  5. iの値を1増やす
  6. iの値が、vto−1 より小さければ、手順3.に戻る
  7. iの値が、vto−1 に等しければ、vtoを1減らす
  8. vtoが0ならば終り。そうでなければ、手順2.に戻る

<プログラム作成のヒント>

結局、どーなるかというと...

バブル・ソートの様子をアニメにしたものが、 これです。

ページの先頭へ

 13補.2 クイック・ソート

バブル・ソートのアニメや、 jdkに添付されているデモ The Sorting Algorithm Demo (1.1)をみて気づかれたかもしれませんが、バブル・ソートでは 一回の入替えで、位置が1つ分しか改善されません。離れたデータを入替え、 入替の効率を改善しましょう。
整数型の配列 vdata の先頭からデータが格納されていて、 データの個数は整数型の変数 num に入っているとします。

クイック・ソートのアプローチは、簡単にいうと以下のとおりです。

<アルゴリズム>

  1. 変数 from と too をそれぞれ整列すべきデータの左端、右端とする
    すなわち、初期値は from = 0; too = num-1;
  2. M = vdata[ (from + too) / 2 ];
  3. int left = from;
    int right = too;
  4. (left <= right) である間、以下の手順7.までを繰り返す
  5.   while( left < too   かつ vdata[left] < M )  left++;
  6.   while( from < right かつ M < vdata[right] ) right--;
  7.   left <= right であれば、vdata[left] と vdata[right] を入替え、
                          left++; right--; とする
  8. right < left になった時、M より小さい値は、from から right の 間に、M より大きな値は、 left から too の間に移動している。 したがって、
    vdata の from から right の間にデータがあれば整列し、さらに
    vdata の left から too の間にデータがあれば整列する。

クイック・ソートの様子をアニメにしたものが、 これです。

ページの先頭へ

 13補.3 ラディックス・ソート

データのキーどうしの比較を行なわずに整列することができます。
たとえば、10進3桁で表現されている次のようなデータがあるとします。
データ

123221013220214 322302110032

まず、1の位に注目して、0から9までに振り分けます。

1の位が01の位が11の位が21の位が31の位が41の位が5...
220221322123214   
110   302013      
      032         

振り分けた結果を、1の位が0のものから順に、1列にまとめます。

220110221322302 032123013214

次に、10の位に注目して、同じように0から9に振り分けます。この時、順序を崩さないよう注意して下さい。

10の位が010の位が110の位が210の位が310の位が410の位が5...
302110220032      
   013221         
   214322         
      123         

同じように、順序を崩さないように、1列にまとめます。

302110013214220 221322123032

同じ手順を、100の位について行えば、全体の整列が完了です。

4  5...
013110214302      
032123220322      
      221         
                  

013032110123214 220221302322

ページの先頭へ


Top Page
更新日:06/27/2003