マージソート
マージソートとは
マージ(merge)とは、「合わせる」、「融合する」といういみの英語です。このソートは、並べ替えるデータを一度ばらばらにして、それを再びマージする過程で並べ替えると、最終的に一つのデータに戻るときには、自然に並べ替えられているというアルゴリズムです。
マージソートの構造
では、実際にもう少し詳しくマージソートによって数値を降順に並べ替える過程を解説していきましょう。
- 並べ替えるデータを、二つに分割し、さらに文化史されたものも再分割します。
- データが完全にばらばらになるまで分割を続けます。
- 分割がおわったら、マージを開始します。並べる際には、先頭から大きなデータを入れていきます。
- 最終的に、すべてのデータのマージが終わると、並べ替えが終了しています。
以上が、マージソートのアルゴリズムです。(図7-1.参照)
図7-1.マージソートの構造
マージソートの実装
以下、各言語でのマージソートの実装を紹介します。
ヒープソート
ヒープソートとは
ヒープソートとは、ヒープ構造3日目に説明したものです。ヒープ構造とは、特殊な二分木です。ヒープとは、親ノードが、子ノードよりも必ず大きい、または小さいという構造を持つデータ構造です。
この仕組みを利用し、ルートノードに最大値（もしくは最小値）が来るようにし、その値を順次取り出すことによってソートを行うのがこのソートの構造です。
アルゴリズムの手順
では、整数値を降順に並べ替えるケースを例にして、実際のアルゴリズムを見てみましょう。
- 並べ替えるデータを二分木に配置します。ルートノードを皮切りに、以後、子ノードに分配していきます。
- 配置したのとは逆方向から、子ノードの値が親ノードより大きければ、入れ替えます。
- すべての探索が終わると、ルートに最大値が残るので、それを取り出し、末端の値をルートに入れます。
- 以後、同じ処理を繰り返します
- すべての処理が終了すると、並べ替え処理がおわります。
ヒープソートの実装
以下、各言語でのヒープソートの実装を紹介します。
クイックソート
クイックソートとは
バブルソートは、アルゴリズムが単純ですが、探索に時間がかかるという問題点がありました。そのためある程度大量のデータをソートするならば、もう少し早いソートアルゴリズムが必要です。そこで、ここではまず、そういったアルゴリズムの一つである、クイックソートについて解説します。
その名の通り、速い（quick）なソートですが、手順が少々複雑です。では、実際にその手順を見てみましょう。
アルゴリズムの手順
クイックソートにおいて、一番最初にやらなければならない処理は、まず、軸要素（じくようそ）と呼ばれる値の決定です。その方法には、さまざまな方法がありますが、ここでは一番単純に、データの先頭にある要素を軸要素とします。(図5-2.参照)
では実際に、昇順でのソートの手順を見てみましょう。アルゴリズムは、以下のようになります。
- 軸要素を決定する。
- 先頭から末端に向かって、軸要素以上の値の探索、逆方向から軸要素の値未満の探索し、見つかったら値同士を交換する。
- 先頭からの探索と、末端からの探索がぶつかった時点で、探索を終了し、交差した時点で、データを二つに分ける。
- 分割したそれぞれの要素で、同様の処理を繰り返し、最終的に、交換する部分がなくなった時点で処理を終了する。
クイックソートの実装
以下、各言語でのクイックソートの実装を紹介します。
 |  |  |
