マージソート

マージソートとは

マージ(merge)とは、「合わせる」、「融合する」といういみの英語です。このソートは、並べ替えるデータを一度ばらばらにして、それを再びマージする過程で並べ替えると、最終的に一つのデータに戻るときには、自然に並べ替えられているというアルゴリズムです。

マージソートの構造

では、実際にもう少し詳しくマージソートによって数値を降順に並べ替える過程を解説していきましょう。

  1. 並べ替えるデータを、二つに分割し、さらに文化史されたものも再分割します。
  2. データが完全にばらばらになるまで分割を続けます。
  3. 分割がおわったら、マージを開始します。並べる際には、先頭から大きなデータを入れていきます。
  4. 最終的に、すべてのデータのマージが終わると、並べ替えが終了しています。

以上が、マージソートのアルゴリズムです。(図7-1.参照)

図7-1.マージソートの構造
バブルソートのアルゴリズム

マージソートの実装

以下、各言語でのマージソートの実装を紹介します。

ヒープソート

ヒープソートとは

ヒープソートとは、ヒープ構造3日目に説明したものです。ヒープ構造とは、特殊な二分木です。ヒープとは、親ノードが、子ノードよりも必ず大きい、または小さいという構造を持つデータ構造です。

この仕組みを利用し、ルートノードに最大値(もしくは最小値)が来るようにし、その値を順次取り出すことによってソートを行うのがこのソートの構造です。

アルゴリズムの手順

では、整数値を降順に並べ替えるケースを例にして、実際のアルゴリズムを見てみましょう。

  1. 並べ替えるデータを二分木に配置します。ルートノードを皮切りに、以後、子ノードに分配していきます。
  2. 配置したのとは逆方向から、子ノードの値が親ノードより大きければ、入れ替えます。
  3. すべての探索が終わると、ルートに最大値が残るので、それを取り出し、末端の値をルートに入れます。
  4. 以後、同じ処理を繰り返します
  5. すべての処理が終了すると、並べ替え処理がおわります。
図7-2.ヒープソートの構造
ヒープソートのアルゴリズム

ヒープソートの実装

以下、各言語でのヒープソートの実装を紹介します。

クイックソート

クイックソートとは

バブルソートは、アルゴリズムが単純ですが、探索に時間がかかるという問題点がありました。そのためある程度大量のデータをソートするならば、もう少し早いソートアルゴリズムが必要です。そこで、ここではまず、そういったアルゴリズムの一つである、クイックソートについて解説します。

その名の通り、速い(quick)なソートですが、手順が少々複雑です。では、実際にその手順を見てみましょう。

アルゴリズムの手順

クイックソートにおいて、一番最初にやらなければならない処理は、まず、軸要素(じくようそ)と呼ばれる値の決定です。その方法には、さまざまな方法がありますが、ここでは一番単純に、データの先頭にある要素を軸要素とします。(図5-2.参照)

では実際に、昇順でのソートの手順を見てみましょう。アルゴリズムは、以下のようになります。

  1. 軸要素を決定する。
  2. 先頭から末端に向かって、軸要素以上の値の探索、逆方向から軸要素の値未満の探索し、見つかったら値同士を交換する。
  3. 先頭からの探索と、末端からの探索がぶつかった時点で、探索を終了し、交差した時点で、データを二つに分ける。
  4. 分割したそれぞれの要素で、同様の処理を繰り返し、最終的に、交換する部分がなくなった時点で処理を終了する。
図7-3.クイックソートの構造
クイックソートのアルゴリズム

クイックソートの実装

以下、各言語でのクイックソートの実装を紹介します。