【基本情報技術者試験】データ整列～その他～

今回は【基礎理論(アルゴリズム)編】データ整列～その他～についてご紹介します。
試験で出題されるデータ整列法には多くの種類がありますが、今回はその中でも応用的で高速な手法について説明していきたいと思います。

シェルソートについて

シェルソート(別名改良挿入法)では、以下の手順を間隔が1になるまで繰り返す事でデータを高速にソートさせています。

全体のデータから、一定の間隔が空いた要素同士でグループを作る
各グループのデータに対して基本挿入法でソートを行う
間隔を狭めて1に戻る

まずはイラストで上の手順を確認してみましょう！
(※基本挿入法の動きは前回の記事で説明してあるので、イラストでは省略しています。)

今回のケースでは上記の手順を全部で3回繰り返しました。
ここで、3巡目の開始時点でデータがどのような並びになっているのかをもう一度確認してみましょう。

上の画像をみるとわかるように、2巡目が終わった段階でほとんどのデータが整列済みとなっています。
前回の記事でも少しお話しましたが、基本挿入法は殆ど整列済みのデータに対しては処理回数が少なくて済むという特徴があります。
今回のケースをみても、1,2と7,8の順序が異なるだけなので、3巡目は直ぐにソート処理が完了します。
すなわちシェルソートとは、間隔が離れたデータに対して処理を行い、基本挿入法が得意とするデータの並びに整える事でソートを高速化させているということになります。(だから改良挿入法と呼ばれるんですね！)

クイックソートについて

クイックソートとは、ピボットと呼ばれる値を定め、その値を基準値としてデータ全体を大小2つのグループに振り分けていくソート方法になります。このようにして大小2つのグループに振り分けが終わったら、各グループごとにピボットを決め直して再びデータの振り分けを行います。この操作を繰り返していくことで、最終的には全てのデータを整列させることができます。
文字だけではわからないので、イラストで確認してみましょう。

上のイメージ図をみると、初めの一回はピボットを6に決めて、データ全体を“6より大きいグループ”と“6より小さいグループ”の2つに分けているのが分かると思います。
このようにしてグループ分けを行い、続けて“6より大きいグループ”と“6より小さいグループ”の中で同じようにピボットの設定とグループ分けを行っています。これを全てのグループの中の要素が1つになるまで続けていけば、最後にはイメージ図のように整列が完了します！

また、今回は各グループの中央付近の値をピボットとして選んでありますが、この基準値を中央ではなく端の方の値にしてしまうと、グループ分けが偏ってしまい、うまく処理が進みません。
クイックソートなどの応用的なソート方法でも、使い方や元のデータの並びによっては計算量が増えてしまうことがあるので、内部の動き(アルゴリズム)をよく理解しておくことが大切です。

ヒープソートについて

ヒープソートとは、データ全体をヒープ木の構造に並び替え、最大値(または最小値)から順番に並べていくソート方法になります。
以前の記事では、「全ての要素が親>子(または子<親)という制約に従って配置された二分木」であるヒープ木をご紹介していましたね！
ヒープソートはそのヒープ木を使ったソート方法になります。
試しに一度ヒープ木を作成する様子を見てみましょう(今回のケースは親>子となるヒープ木です。)
上のイメージ図では、「親と子の値を比較して、大小関係が異なればデータを入れ替える」という操作を木構造の葉から根に向かって行っています。なお、入れ替えが発生した場合は、入れ替えた要素がその新しい子要素と正しい大小関係になっているかを再度確認する必要があります。(最後に2と6を入れ替えているのがその部分に該当します。)

さて、こうしてヒープ木を作成すると、根となる要素には最大値(または最小値)が配置されることになります。
つまり、ヒープ木を構成したのち根のデータ(最大/最小値)を取り出して、再度残るデータでヒープ木を作る・・・という作業を続けていけば、データを最大値(または最小値)から順番に取り出し、並べていくことができるわけです。
このようにしてデータを並べていきソートを完了させるのが、ヒープソートとなります。

以上で応用的なソート方法についての紹介は終わりです。
前回の基本的なソート方法とも見比べながら理解を深めていってくださいね！