アルゴリズムの話
Story of algorithm


目次

 1ページ目
 第0話 ソーティングって何?
 第1話 バブルソート
 第2話 単純選択ソート
 第3話 単純挿入ソート
 第4話 ハッシュ法の概要
 第5話 次回の予定

 関連ページ
 遺伝的アルゴリズム


現在リニューアル中です。このコンテンツについては今後大量更新の予定ありです。(2010/03/22)


ソーティングって何?


まずはアルゴリズムの基本中の基本、ソーティング(整列)の話を始めましょう。

ソーティングというのは要は”並べ替え”のことで、ランダムな数値データなんかを 昇順(小さい順)や降順(大きい順)に並べ替えることです。


例えば {10, 5, 38, 15, 2, 49, 5, 24, 67, 14} というランダムな数値があったとすると

昇順に {2, 5, 5, 10, 14, 15, 24, 38, 49, 67} と並べ替えたり
降順に {67, 49, 38, 24, 15, 14, 10, 5, 5, 2} と並べ替えることをソーティング(ソートする)と言います。


ソーティングのアルゴリズムには色々と種類があって、有名どころでは バブルソート、選択ソート、シェルソート、 マージソート、ヒープソート、クイックソート などがあり、それぞれ改良版なども数多く考案されています。

他にも基数ソートとかビンソートなんていうのもあります。

こんなにソートの種類があると一体どれを使えばいいものか迷ってしまいますが、まあ結論をいっちゃうと 「状況に応じて使い分けろ!」ということになります。そのためには各ソートの長所・短所を知る必要があるわけです。 具体的な特徴は次回以降1つずつ見てゆくとして、今回は大雑把に分類をしてみましょう。

ソートの評価基準の一つに時間計算量という概念があります。ただ、この話を始めると面倒なことになるので 単純にソーティングの計算速度(つまりどれだけ並べ替えに時間が掛かるか)を基準に上記のソートを分類してみましょう。

低速:バブルソート、選択ソート

中速:シェルソート

高速:マージソート、ヒープソート、クイックソート

この分類はかなり重要です。例えば、同じ数列をソーティングするにしても選択ソートだと3時間掛かるものが クイックソートだと30秒で出来たりします。


バブルソート


最初はバブルソートの説明から始めましょう。
バブルソートは低速ではあるものの非常に安定したアルゴリズムであると言われています。

安定というのは

  ↓        ↓
{10, 5, 38, 15, 2, 49, 5, 24, 67, 14}というように同じ数値があった場合、これをソートした結果
(便宜上最初の5を 5A 、後ろの5を 5B とします)

{2, 5A, 5B, 10, 14, 15, 24, 38, 49, 67} となるのを「安定している」
{2, 5B, 5A, 10, 14, 15, 24, 38, 49, 67} となるのを「安定していない」といいます。

「同じ数値なんだからどっちが先になろうが関係ないじゃん」と思われるかもしれませんが、この数値が 他のデータと対応関係を持っている場合、同一数値でも位置関係というのが重要になってくるんです。

基本的に高速なソートほど安定性が低いという傾向があるようです。もちろん低速だから必ずしも安定しているとは 言えませんが・・・・

話を戻しましょう。バブルソートは安定していること以外に、非常に単純なアルゴリズムですので サクッとコーディングできるのが特徴です。少量のデータのソートに向いているといえるでしょう。

それではアルゴリズム(手順)の説明です。

例として{10, 5, 38, 15, 2, 49, 5, 24, 67, 14}という数列を昇順にソートする場合、 バブルソートでは隣り合った要素同士を比較し、前の値が後ろの値より大きければ 値を交換して次ぎの要素に移るということを繰り返します。

 ↓ ↓
{10, 5, 38, 15, 2, 49, 5, 24, 67, 14}	(10と5を交換して 次ぎへ↓)
    ↓  ↓
{5, 10, 38, 15, 2, 49, 5, 24, 67, 14}	(このままで 次ぎへ↓)
        ↓  ↓
{5, 10, 38, 15, 2, 49, 5, 24, 67, 14}	(38と15を交換して 次ぎへ↓)
            ↓ ↓
{5, 10, 15, 38, 2, 49, 5, 24, 67, 14}	(38と2を交換して 次ぎへ↓)

そして比較が最後の要素まで到達したら、1番最初に戻ります。

                               ↓ ↓
{5, 10, 15, 2, 38, 5, 24, 49, 67, 14}	(67と14を交換して 最初に戻る)
↓  ↓
{5, 10, 15, 2, 38, 5, 24, 49, 67, 14}	(このままで 次ぎへ↓という風に)
    ↓  ↓
{5, 10, 15, 2, 38, 5, 24, 49, 67, 14}	(繰り返していきます\(^O^))

で、いつまで繰り返すのかというと、値の交換がなくなるまでです。
値の交換がなくなればその時点でソートは終わっていますので処理も終わらせましょう。

ではC言語でのプログラム例をこちらに載せときます。(他言語の例もそのうち・・・)
処理の途中経過も見れるようにしてますので、実行して確認してみてください。

(バブルソートによる整列のソース)



単純選択ソート


次ぎは単純選択ソートについてお話しましょう。

始めに断っておきますが、このソートはあまりに効率が悪過ぎて使い物になりません。 計算量が膨大になる上に安定性もまるで無し・・・ダメダメですな。

しかし、単純であるが故にソートを学ぶ第一歩としては適切でありましょう。

さて、早速単純選択ソートの手順を説明しますが、ソートするデータは前回同様
{10, 5, 38, 15, 2, 49, 5, 24, 67, 14}←これを使いましょう。

単純選択ソートのアルゴリズムはバブルソート並に簡単です。

上記のデータを昇順(小さい順)にソートすると、単純選択ソートの場合、左の要素から順に 小さい数字が決定されていきます。バブルソートは右の要素から順に大きい数字が決定されて いきますので全く対照的ですね。(えっ?そうだったっけ?と思った人はもう1回バブルソートを確認すべし!)

単純選択ソートではまず一番左側の要素とそれ以降の要素を順に比較していき、比較している要素が 一番左側の要素より小さければ交換する、ということを繰り返します。

 ↓ ↓
{10, 5, 38, 15, 2, 49, 5, 24, 67, 14}	(10と5を交換して 次ぎへ↓)
 ↓     ↓
{5, 10, 38, 15, 2, 49, 5, 24, 67, 14}	(このままで 次ぎへ↓)
 ↓         ↓
{5, 10, 38, 15, 2, 49, 5, 24, 67, 14}	(このままで 次ぎへ↓)
 ↓            ↓
{5, 10, 15, 38, 2, 49, 5, 24, 67, 14}	(5と2を交換して 次ぎへ↓)

そして比較が最後の要素まで到達したら、2番目の要素とそれ以降の要素の比較に移ります。

 ↓                               ↓
{2, 10, 38, 15, 5, 49, 5, 24, 67, 14}	(このままで 2番目の要素との比較へGO!↓)
    ↓  ↓
{2, 10, 38, 15, 5, 49, 5, 24, 67, 14}	(このままで 次ぎへ↓)
    ↓      ↓
{2, 10, 38, 15, 5, 49, 5, 24, 67, 14}	(このままで 次ぎへ↓)
    ↓         ↓
{2, 10, 38, 15, 5, 49, 5, 24, 67, 14}	(10と5を交換して 次ぎへ↓という風に)
    ↓             ↓
{2, 5, 38, 15, 10, 49, 5, 24, 67, 14}	(繰り返していきます\(^O^))

以上の比較を延々と繰り返していって、最後の1つ手前の要素と最後の要素の比較が 終わればそれでソーティング終了ということになります。

                              ↓  ↓
{2, 5, 5, 10, 14, 15, 24, 38, 67, 49}	(67と49を交換して↓)
                              ↓  ↓
{2, 5, 5, 10, 14, 15, 24, 38, 49, 67}	(これでやっと終了\(^O^)/)

今回の例では最後の最後まで値の交換がたまたまありましたが、 単純選択ソートは例え途中でソーティングが完了した場合でも無駄な比較を延々と繰り返すことになります。 かなり非効率です。

極端な例でいいますと、

{5, 2, 5, 10, 14, 15, 24, 38, 67, 49}

という数列をソートする場合に単純選択ソートはものの見事にその間抜けぶりを遺憾無く発揮してくれることでしょう。 今回もC言語でのプログラム例を載せときますので、自分でカウンタをつけてこの数列のソートを バブルソートと単純選択ソートとで比較してみてください。

(単純選択ソートによる整列のソース)



単純挿入ソート


今回は単純挿入ソートの話です。単純挿入ソートも見事な低速ぶりなのですが、他の低速ソートに比べて 用途は幅広いと思います。個人的にはこのソートは"挿入法というテクニックをソーティングに 応用したもの"程度に思ってますので、このアルゴリズムの重要なところはソート自体にではなく "配列にデータを挿入"していく部分にあると考えています。

前置きはこれくらいにして、ソート手順の説明に入りましょう。
{10, 5, 38, 15, 2, 49, 5, 24, 67, 14}←今回もこのデータをソーティングです

単純挿入ソートもアルゴリズムは簡単なので肩の力を抜いていきましょう!

単純挿入ソートの原理は「既にソート済みのデータ列に対して新たなデータを加えていく」というものです。 ですが、上のデータを見ていただくと分るようにちっともソート済みじゃありません。ですから、 まずは1番最初のデータ(この場合は10)が既にソート済みであるということにして2番目の要素をその データ列(まだ列じゃないけど)に対して挿入することを考えます。

 ↓ ↓
{10, 5, 38, 15, 2, 49, 5, 24, 67, 14}	(10というソート済みのデータ列に対し)
 ↓ ↓
{5, 10, 38, 15, 2, 49, 5, 24, 67, 14}	(数値の大小を比較した上で5を挿入)

すると次は{5, 10}というソート済みのデータ列に対して、38を挿入します。

    ↓  ↓
{5, 10, 38, 15, 2, 49, 5, 24, 67, 14}	(38は10より大きいので配列の3番目の要素に挿入)

そして今度は{5, 10, 38}というソート済みのデータ列に対して、15を挿入というように見ていきます。

        ↓  ↓
{5, 10, 38, 15, 2, 49, 5, 24, 67, 14}	(15と38を比較すると15の方が小さい・・・)
    ↓      ↓
{5, 10, 38, 15, 2, 49, 5, 24, 67, 14}	(けれど10と比較すると15の方が大きいので)
      ↓
{5, 10, 15, 38, 2, 49, 5, 24, 67, 14}	(15はここに挿入することになります^^;)

せっかくですからもう少しソートの様子を見てみましょう。

          ↓  ↓
{5, 10, 15, 38, 2, 49, 5, 24, 67, 14}	(2を38と比較)
        ↓     ↓
{5, 10, 15, 38, 2, 49, 5, 24, 67, 14}	(15と比較)
   ↓          ↓ 
{5, 10, 15, 38, 2, 49, 5, 24, 67, 14}	(10と比較・・・まだ挿入場所見つからず)
↓            ↓ 
{5, 10, 15, 38, 2, 49, 5, 24, 67, 14}	(5よりも小さいってことは・・・)
↓ 
{2, 5, 10, 15, 38, 49, 5, 24, 67, 14}	(2はここに挿入されることに決定(^O^))

以上の作業を繰り返して、最後の要素の14を挿入し終えたらソート終了です。さて、この処理でポイントとなるのは データがある部分に挿入されたとすると、それ以降のデータの配列位置がずれていくところです。例えば上の 例では、2が配列の最初に挿入されたので、5, 10, 15, 38 のデータは配列の位置が1つずつ後ろに 下がってますよね。その部分がポイントです。

今回は2つソースを載せておきます。どこらへんが違うか比較してみてください。

(単純挿入ソートによる整列のソース)



ハッシュ法の概要


前回までソートの話をしていましたが、今回から探索アルゴリズムの話に突入します。

探索とは、目的のデータがどこにあるのか探す操作のことを指します。言葉の通りです。 探索のアルゴリズムとしては、線形探索法や二分探索法など幾つかの代表的な方法が先人の手により 考えられており、今回お話しするハッシュ法もそんな代表的な探索法の一つです。

ちなみに線形探索法とは、配列や連結リストなどの要素を先頭から順々に調べていくという最も シンプルな探索法です。解説もこの説明で終了してしまうほどシンプルです。

これからお話しするハッシュ法は、線形探索に比べると少々ややこしいですが、順を追って理解していけば 恐れるに値しません。腰をすえて、じっくりと理解してやりましょう。

ハッシュ法とは、データ量に関係なくデータの探索を一定時間で行うことが可能な探索法の一種です。 データ構造は配列で実装可能で、計算量はO(1)になります。

さて、ここで具体例を用いてハッシュ法について理解していきましょう。

あるクラスの英語テスト結果をデータとしてもつ配列を用意したいと思います。生徒たちは学生番号で 識別されるものとします。行いたい探索は「学生番号○○の英語の点数は何点か?」です。

ここで、生徒を識別する(学生番号)のことを「キー」と呼び、(英語の点数)のことを「データ」 と呼ぶことにします。ハッシュ法の原理は、この「キー」の値を「データ」を格納している配列の添え字に関連付けることです。

例えば、生徒数8名のクラスで以下のようなテスト結果であったとしましょう。

学籍番号 1 点数 54
学籍番号 2 点数 30
学籍番号 3 点数 100
学籍番号 4 点数 37
学籍番号 6 点数 80
学籍番号 7 点数 92
学籍番号 8 点数 54
学籍番号 9 点数 77


なお、学籍番号5の生徒は両親の都合で転校しちゃいました(ノД`)。バイバイ5番くん・・・。

今回のようなケースの場合、配列の要素数は10くらいにして、 以下のようにデータを挿入するとよいでしょう。

int test[10];		//C言語の場合
int[] test = new int[10];	//Javaの場合

test[0] = 0;
test[1] = 54;
test[2] = 30;
test[3] = 100;
test[4] = 37;
test[5] = 0;
test[6] = 80;
test[7] = 92;
test[8] = 54;
test[9] = 77;


これだと、学籍番号0と5は存在しないはずなのに、0点という点数を取っていることになるので、 そもそも学生が存在しないのか、単に在籍する生徒が0点を取っただけなのかを区別するために、 別途フラグが必要になります。その点についは、各自で方法を考えてください。

上記のデータ構造の場合は、線形探索法で十分でしょう。例えば学籍番号7の生徒の英語の点数を 知りたければ以下のようにすれば良いだけです。

//これで学籍番号7の生徒の英語の点数を取得できます
test[7]

//標準出力に書き出したいなら
printf("学籍番号7の英語の点数は%dです\n", test[7]);			//C言語の場合
System.out.println("学籍番号7の英語の点数は" + test[7] + "です");//Javaの場合


では、話を次の段階へ移しましょう。

先の例では、学籍番号が都合よく0〜9に収まってくれていましたから簡単でしたが、もし学籍番号が次のように 割り振られていたらどうすればよいでしょう。

学籍番号 200801 点数 54
学籍番号 200802 点数 30
学籍番号 200803 点数 100
学籍番号 200804 点数 37
学籍番号 200806 点数 80
学籍番号 200807 点数 92
学籍番号 200808 点数 54
学籍番号 200809 点数 77


先ほどの例と、同じ考え方に基づきデータ構造を構築するとなると以下のようになります。


//C言語の場合
int test[201000];		//C言語の場合
int[] test = new int[201000];	//Javaの場合

test[0]		 = 0;
test[0]		 = 1;
・・・・
test[200800] = 0;
test[200801] = 54;
test[200802] = 30;
test[200803] = 100;
test[200804] = 37;
test[200805] = 0;
test[200806] = 80;
test[200807] = 92;
test[200808] = 54;
test[200809] = 77;
・・・・
test[200999] = 8;
test[200999] = 0;


え〜と・・・設定や処理系によっても異なるのですが、この規模になると非効率とかどうこう以前に メモリの領域確保に失敗する可能性があります。

配列はとんでもない大きさになりましたが、線形探索は以前として有効です。例えば、学籍番号200807の 英語の点数を知りたければtest[200807]とすれば、計算量O(1)で一定時間で探索完了です。データ量は 関係ありません。

でも、このままじゃダメでしょ・・・このままじゃ・・・常識的に考えて・・・

今回の問題を受けて、次回はいよいよ解決編。
解決のための必殺ツール「ハッシュ関数」が炸裂!乞うご期待!!


次回の予定


ハッシュ法の続きです。





アルゴリズムの話Topへ