定番アルゴリズムを徹底理解！

　このパートでは，プログラミングを勉強するうえで欠かせないアルゴリズムの中でも定番中の定番を紹介します。ソート（並べ替え）やサーチ（検索）などの機能は今では標準のライブラリとして提供されています。実用的なプログラムを作るときにそのものずばりをいちいち書く機会は少ないかもしれません。しかし定番のアルゴリズムは，様々に形を変えて普段のプログラミングに登場します。

　解説を読んで仕組みがわかったら，ぜひそれをプログラムにしてみてください。読んだだけではプログラムを書けるようにはなりませんし，プログラムを書いてみて初めて，実は十分に理解できていなかったと気付くことがよくあります。しかもアルゴリズムは特定のプログラミング言語に依存しないので，一度身に付ければ，後でどんな言語を学ぶ場合でも役に立ちます。

　1番目から6番目まではソートのアルゴリズム，7番目から9番目まではサーチのアルゴリズムです。一つひとつ作って動作を確かめたら，大量のデータを与えて性能を比較してみましょう。安直な方法では解決できない問題でも優秀なアルゴリズムがあればいとも簡単に解決できることを実感できます。

１．挿入ソート
トランプ手札の並べ替えを思い出せば簡単

　「ソート（sort）」とは，たくさんのモノがあるときに，それらをある特定のルールに従って，例えば値の小さいものから大きいものに順に並べ替えることです。実生活では，トランプの手札を並べ替えるときや，お年玉付き年賀ハガキを番号の下2ケタで並べ替えるといった作業が該当します。

　こうした並べ替え作業をする方法はいくつもあります。多くの人がまず思いつくのは，並べ替える対象を一つ選んで，それを適切な位置に挿入していくことでしょう。トランプの手札を並べ替える場合であれば，例えば，一番右のカードを抜いて，カードの数字に応じて適切な場所に差し込んでいく，という作業を何度か繰り返せば良いのです。

　これを実現するアルゴリズムが「挿入ソート」です。つまり，未ソートのデータを一つひとつ，ソート済みの列の適切な位置に差し込んでいくわけです（図1）。アイデア自体はとても簡単ですね。

図1●挿入ソートのアルゴリズム。未ソートのデータを，ソート済みの列の適切な個所に挿入していく

　でも挿入ソートのアルゴリズムをプログラムで記述しようとすると少し複雑になります。ハガキやトランプなら無造作に差し込んでしまえばいいのですが，プログラムではデータをいちいち格納したり，取り出したりする必要があるからです。こうしたプログラムでは，ソートの対象にするデータを配列に格納するのが一般的です。配列のデータを並べ替える場合には，挿入先の場所（配列要素）を空けなければなりません＊1。

図2●配列内で挿入ソートを実行する際の手順

　図2は配列のデータに対して挿入ソートを実行している途中の様子です。未ソート部分の先頭のデータ（ここでは47）を取り出して，それをソート済み部分の適切な個所に挿入しようとしています。まず，ソート済み部分の末尾のデータ（77）と比較します。取り出したデータのほうが小さいので，末尾のデータを今までそのデータが保存されていた個所にコピーして場所を空けます。次に，対象を一つ先頭に向かってずらし，59と比較します。すると，また自分のほうが小さいので，仮の挿入場所を一つずらします。4回目の比較対象となる5は自分より小さいので，そこに挿入すればよいことがわかります。コードはリスト1のようになります。

リスト1●挿入ソートのコード（Visual Basic 2005）

　挿入ソートはわかりやすいのですが，ソートの対象にするデータの個数が増えると，計算量（繰り返し回数）が爆発的に増えてしまいます。詳しい計算式は省きますが，繰り返し回数はデータ個数の2乗に比例します＊2。つまり，データの個数が10倍になるごとに繰り返し回数がおおむね100倍になります。このように，繰り返し回数がデータ個数の2乗に比例するアルゴリズムには，どんな場面にでも対応できるだけの汎用性はありません。

　ただし，挿入ソートは非常に高速に動作する場合があります。最も高速なのは，ソート済みのデータをソートしようとしたときです。

　「そんなの当たり前じゃないの」という声が聞こえてきそうですが，そうではありません。そのデータがソート済みかどうかわからない場合には，ソートのアルゴリズムを適用して処理を行う必要があるからです。

　挿入ソートではデータがソート済みの場合，挿入を試みる最初の比較（図2では47と77との比較に相当）で必ず自分より小さいデータが見つかり，その場で挿入場所が確定します。このため，（データ個数－1）回の繰り返しでソートが終了します。処理がシンプルであることも相まって，挿入ソートはこの場合に限って，一般的に高速とされるどのアルゴリズムよりも高速にソートできます。ソート済みのデータ列の末尾にデータを何個か追加して全体をソートし直す，といった場合も有効です。