ソートアルゴリズム
ソートとは
サーチアルゴリズムに続き、ここでは3回にわたり、ソートアルゴリズムについて説明します。ソートとは、「並べ替え」の意味です。数値データを、大きい順、もしくは小さい順に並べ替える処理のことを言います。
なお、データを小さい順に並べ替えることを、昇順（しょうじゅん）、大きい順に並べ替えることを、降順(こうじゅん)と言います。（図5-1.参照）
図5-1.ソート（昇順と降順)
ただ、並べ替えの対象になるのは、なにも数値とは限りません。英単語を辞書の順に並べ替えたりするような処理も、ソートです。このように、ソートアルゴリズムは、実に多岐にわたって利用されるアルゴリズムなのです。
バブルソート
バブルソートとは
最初に紹介するのは、バブルソートと呼ばれるソートアルゴリズムです。バブルとは、日本語で泡を意味する言葉です。ではいったい、なぜ「泡」と呼ばれるのでしょうか。それは、このアルゴリズムの仕組みに由来しています。まずは、昇順でのソートでその仕組みを見てみましょう。
- リストの先頭から、要素を取り出す。（これを、要素①とする）
- 次の要素（要素②とする）と、要素①を比較する。
- 要素①が、要素②より大きければ、値を交換する。
- 要素②の次の要素を、新たに要素②とし、2.に戻る。
- 末端まで処理が終われば、新たに要素①を、次の要素に、さらにその次を要素②として、2.に戻る
- 要素①が、末端より一つ前まで終了したら、処理を終了する。
以上が、バブルソートのアルゴリズムです。バブルソートと呼ばれるのは、小さい要素が浮かびあがってくるように見えることに由来します。(図5-2.参照)
図5-2.バブルソートの構造
バブルソートの実装
以下、各言語でのバブルソートの実装を紹介します。
メリットとデメリット
バブルソートのメリットは、なんと言っても実装の容易さです。さまざまなソートアルゴリズムの中では、実装がもっとも簡単なアルゴリズムの一つといえます。
それに対し、デメリットは、処理のステップ数の多さです。要素の個数をnとすると、必ず n(n - 1)/2 回のスキャンが必要になります。つまり、リストの要素が1000あれば、499500回のスキャンが必要になるのです。
このようなことから、バブルソートは、要素数が少ない簡単なリストで用いることが好ましいアルゴリズムです。
選択ソート
選択ソートとは
選択ソートは、バブルソートの改良型と言えます。配列の最小値(最大値)を持つ要素を探し、それと先頭の要素と交換することで整列を行うアルゴリズムです。昇順でのソート処理の流れは以下のようになります。
- リストの先頭要素を仮の最大値とする。
- 2番目以降の要素を一つずつ見て、仮の最大値よりも大きければ、その番号を覚えておく。
- 一通り処理が終わったあと、2番目以降に仮最小値以下のものがあれば、その要素と先頭の要素を交換する。
- 以下、2番目以降にも同様の処理を繰り返す。
これが、選択ソートの処理の流れです。（図5-3.参照）
図5-3.選択ソートの構造
選択ソートの特徴
選択ソートは、バブルソートによく似ていますが、交換の手順が1回で済む分だけ、若干バブルソートよりも処理が速いという特徴があります。
選択ソートの実装
以下、各言語での選択ソートの実装を紹介します。
挿入ソート
挿入ソートとは
挿入ソートとは、あらかじめ整列が終わっている配列に、データを挿入するアルゴリズムで、最も基本的なアルゴリズの一つとして知られています。手順は以下の通りです。
- 先頭から、並んだ要素のうち最初の2つを取り出し比較します。
- 最初の要素が、二番目の要素よりも大きければ、並び替えます。
- 次に、3つ目の要素と並べ替えた2つの要素を比べ、適切な位置に挿入します。
- 以後、終端まで同様の処理を繰り返します。
この流れを図にすると、以下のようになります。(図5-4.参照)
図5-4.挿入ソートの構造
挿入ソートの特徴
挿入ソートの特徴は、人間が並べ替えを行う時に考え方に非常に近いという点です。そのため、理解しやすいソートであると言えるでしょう。さらに、もともとのリストがソート済み状態に近ければ比較的高速に動作しますが、逆順に並んでいるとからり時間を要します。
つまり、もともとの要素の並び方によって処理時間が左右されてしまうアルゴリズムなのです。
挿入ソートの実装
以下、各言語での挿入ソートの実装を紹介します。
シェルソート
シェルソートとは
前述の通り、選択ソートには並び方によって処理時間が大きく左右されるという欠点がありました。これを改良したのが、シェルソートです。シェルの名はアルゴリズムの考案者の名前に由来します。つまり、「シェルさんが作ったソートアルゴリズム」というわけです。
考え方としては、リスト全体をいくつかに分け、それぞれで挿入ソートを行い、それを徐々に詰めていく、という考え方です。具体的な手順は以下の通りです。
- 要素全体を、いくつかの要素に分けます。
- 分割したそれぞれの要素内で挿入ソートの処理を行います。
- 挿入ソート処理が終わった、隣接する配列同士を結合し、さらに挿入ソートを行います。
- 最終的に、全体が統合されるまで、同様の処理を繰り返します。
要素の分解の仕方は、要素全体を数個置きに2個ずつの組み合わせに分けていき、それを統合するというような方法が一般的です。
例えば、長さが8のリストであれば、4個置きに2個の要素の組み合わせを最初に作ります。この並べ替えが終わると、今度はその倍、4個の組み合わせを2個やはりこれも一つのリスト要を2個おきに分けて2つ作ります。
それぞれの分割内のソートのアルゴリズムは、前述の通り挿入ソートを用います。これを図解すると、以下のようになります。(図5-5.参照)
図5-5.シェルソートの構造
シェルソートの特徴
シェルソートは、すでに説明したとおり、全体を細かく分けて少しずつ並べ替えながら統合していくことで、挿入ソートでの問題点を克服し、より高速になったアルゴリズムです。ただ、後述するクイックソートに比べれば処理速度が劣ります。
シェルソートの実装
以下、各言語でのシェルソートの実装を紹介します。
 |  |  |
