今回は、基本情報技術者試験でもよく出題されている『整列アルゴリズム』について、基本的な整列アルゴリズムの種類6つとそれらに関する演習問題をご紹介していこうと思います。
インプットもアウトプットも同時に試せてしまうため、本記事を通して『整列アルゴリズム』に関する知識を確かなものにしてしまいましょう。
また、本記事で扱っている演習問題は、大半が基本情報技術者試験の過去問になるため、試験対策にもなります。
ぜひ最後まで見ていってください。
この記事でわかること
- 整列アルゴリズムについて
- 6つのソートについて
- 整列アルゴリズムに関する演習問題
目次
用語解説
では、まず初めに整列アルゴリズムや、整列アルゴリズムの種類である基本的なソートについてそれぞれ解説していこうと思います。
ちなみに、今回紹介するソートは以下の6つです。
- バブルソート
- 選択ソート
- 挿入ソート
- クイックソート
- ヒープソート
- マージソート
では、それぞれについて以下で詳しく説明していきます。
整列アルゴリズムとは？
複数のデータからなるデータ列を、昇順・降順で並び替えるためのルールのことを整列アルゴリズムと言います。
例えば、以下のようなデータ列、私たちであれば簡単に小さい順に並び替えることが出来ますよね。
しかし、コンピュータにとっては、このような作業も、人間からあるルールを与えないと難しいのです。
なので今回は、コンピュータに与えるルールのようなものを6つほどご紹介していくことになります。
①：バブルソート
バブルソートとは、隣り合ったデータ同士の比較を繰り返して、整列を行うアルゴリズムです。
最大値が、徐々に端の方へ、泡が浮き上がるように移動していく様子からバブルソートと呼ばれています。
上図はバブルソートの適用例ですが、隣同士を比較して、データの入れ替えを行うことで、右側に徐々に確定した要素を作っていますよね。
全てのデータが確定するまで比較を続けることで、最終的に整列したデータを得ることが出来るのです。
②：選択ソート
選択ソートは、最小値と一番左の要素の入れ替えを繰り返して、整列を行うアルゴリズムです。
ちなみに、ここでいう一番左の要素とは、未確定データ列の中の一番左の数字ということになります。
図の通り、最小値を探してきて、一番左のものと入れ替えるだけなので非常にシンプルですよね。
③：挿入ソート
挿入ソートは、未確定のデータから要素を一つ取り出して、それを確定済みのデータ列へ挿入していくことで、整列を行うアルゴリズムです。
下の図では、一回目のサイクルで『6』を、2回目のサイクルで『2』を、3回目のサイクルで『4』を確定済みのデータ列へ挿入しています。
④：クイックソート
クイックソートは、データ列をピボットと呼ばれる基準値よりも大きいか小さいかで分割するといった操作を繰り返すことによって、整列を行うアルゴリズムです。
下の図でも、ピボットを適当に設定して、それより小さいグループと大きいグループに分けていますよね。
分けた後は、再びできた小さいデータ列の中でピボットを決めて先ほどの操作を繰り返します。
⑤：ヒープソート
ヒープソートは、未整列のデータからヒープを作成することによって、整列を行うアルゴリズムです。
ヒープの『根に最大値が移動する』といった性質を用いて、データの整列を行っています。
ちなみに、上図はヒープソートを用いた整列の一例ですが、最後まで載せるとすごい量になってしまうため、途中までの操作を示しています。
⑥：マージソート
マージソートは、いったんデータ列を要素ごとに分割して、その後並び替えながら併合することによって、整列を行うアルゴリズムです。
演習問題
続いては過去問をもとにした演習問題です。
インプットした知識を演習を通じてアウトプットして、知識の定着を図りましょう。
演習問題①
バブルソートの説明として，適切なものはどれか。
[応用情報技術者令和3年秋期 午前問5]
ア. ある間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が1になるまでこれを繰り返す。
イ. 中間的な基準値を決めて，それよりも大きな値を集めた区分と，小さな値を集めた区分に要素を振り分ける。次に，それぞれの区分の中で同様の操作を繰り返す。
ウ. 隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返す。
エ. 未整列の部分を順序木にし，そこから最小値を取り出して整列済の部分に移す。この操作を繰り返して，未整列の部分を縮めていく。
演習問題②
データの整列方法に関する記述のうち，適切なものはどれか。
[基本情報技術者平成20年春期 午前問13]
ア. クイックソートでは，ある一定間隔おきに取り出した要素から成る部分列をそれぞれ整列し，更に間隔を詰めて同様の操作を行い，間隔が1になるまでこれを繰り返す。
イ. シェルソートでは，隣り合う要素を比較して，大小の順が逆であれば，それらの要素を入れ替えるという操作を繰り返して行う。
ウ. バブルソートでは，中間的な基準値を決めて，それよりも大きな値を集めた区分と小さな値を集めた区分に要素を振り分ける。
エ. ヒープソートでは，未整列の部分を順序木に構成し，そこから最大値又は最小値を取り出して既整列の部分に移す。これらの操作を繰り返して，未整列部分を縮めていく。
演習問題③
クイックソートの処理方法を説明したものはどれか。
[基本情報技術者平成30年秋期 午前問6]
ア. 既に整列済みのデータ列の正しい位置に，データを追加する操作を繰り返していく方法である。
イ. データ中の最小値を求め，次にそれを除いた部分の中から最小値を求める。この操作を繰り返していく方法である。
ウ. 適当な基準値を選び，それより小さな値のグループと大きな値のグループにデータを分割する。同様にして，グループの中で基準値を選び，それぞれのグループを分割する。この操作を繰り返していく方法である。
エ. 隣り合ったデータの比較と入替えを繰り返すことによって，小さな値のデータを次第に端のほうに移していく方法である。
演習問題④
データ列が整列の過程で図のように上から下に推移する整列方法はどれか。ここで，図中のデータ列中の縦の区切り線は，その左右でデータ列が分割されていることを示す。
ア. クイックソート
イ. シェルソート
ウ. ヒープソート
エ. マージソート
演習問題⑤
四つの数の並び(4，1，3，2)を，ある整列アルゴリズムに従って昇順に並べ替えたところ，数の入替えは次のとおり行われた。この整列アルゴリズムはどれか。
(1，4，3，2)
(1，3，4，2)
(1，2，3，4)
ア. クイックソート
イ. 選択ソート
ウ. 挿入ソート
エ. バブルソート
まとめ
今回は、整列アルゴリズムについて、その意味や種類について説明してきたのですがいかがだったでしょうか。
演習問題を見た方ならわかると思うのですが、試験ではそれぞれの種類に関する説明を選択する問題がよく出題されます。
整列アルゴリズムは種類が非常に多いですが、その中でも特に大切なものを6つ紹介してきたので、この機会に完璧に覚えてしまいましょう。