整列・併合・探索のアルゴリズム

テクノロジ系 > 大分類1 基礎理論 > 中分類2 アルゴリズムとプログラミング > 2.アルゴリズム > (2)代表的なアルゴリズム > ① 整列・併合・探索のアルゴリズム

① 整列・併合・探索のアルゴリズム
整列のアルゴリズム，併合のアルゴリズム，探索のアルゴリズムを理解する。
用語例選択ソート，バブルソート，マージソート，挿入ソート，シェルソート，クイッ
クソート，ヒープソート，線形探索法，2 分探索法，ハッシュ表探索法，シノニム対策

アルゴリズムとは、処理手順のことを言います。アルゴリズムはこれまでの研究結果によって、この場合はこういう処理手順が良いということが明らかになっているものが多くあります。整列、併合、探索のアルゴリズムはプログラムの処理の中で非常に良く用いられる分野であるため、多くの研究がされています。ある事柄を実現するためのアルゴリズムは一つとは限りませんが、より正確かつ効率的なプログラムを組みためには定番のアルゴリズムを知っておく必要があります。

整列アルゴリズム
探索のアルゴリズム
整列・併合・探索のアルゴリズムのポイント

整列アルゴリズム

整列とは、データをある基準に沿って並び替えることです。併合とは、二つの整列済みのデータの並びがあったときに、その二つを一つの整列されたデータにすることです。併合のアルゴリズムは整列の応用バージョンで、応用情報技術者試験においては整列を知っておけば溶ける問題が多いため省きます。

整列アルゴリズムはシラバスの用語例によれば以下の7つが挙げられています。

選択ソート
バブルソート
マージソート
挿入ソート
シェルソート
クイックソート
ヒープソート

このうち、選択ソート、バブルソート、挿入ソートの3つが基本3ソート、残りが応用4ソートと呼ばれています。基本3ソートはアルゴリズムが単純ですが効率は悪く、応用4ソートはアルゴリズムは複雑ですが効率が良いです。

選択ソート

選択ソートは未整列のデータ列の中から最小値（または最大値）を探して整列し、整列部分・未整列部分に分け、未整列部分でまた同じように最小値を探して整列します。この操作を全体が整列部分になるまで繰り返します。計算量はO(n²)になります。

バブルソート

バブルソートは隣り合う要素を比較して、大小が逆であれば入れ替えを行う操作を繰り返すアルゴリズムです。計算量はO(n²)になります。

過去問 令和5年秋期問6（高度試験午前Ⅰ 問3）

あるデータ列を整列したら状態0から順に状態1，2，・・・，Nへと推移した。整列に使ったアルゴリズムはどれか。

　状態0　3，5，9，6，1，2
　状態1　3，5，6，1，2，9
　状態2　3，5，1，2，6，9
　　　　　・
　　　　　・
　状態N　1，2，3，5，6，9

ア．クイックソート
イ．挿入ソート
ウ．バブルソート
エ．ヒープソート

解答：ウ

マージソート

未整列のデータ列を分割していき、それをマージを繰り返して一つの整列データにする方法です。マージをするたびに整列されていきます。計算量はO(nlog n)になります。

挿入ソート

整列データの中に未整列データを適切な位置に入れていくアルゴリズムです。すでに整列データがある場合には早く処理ができます。計算量はO(n²)です。

シェルソート

一定間隔ごとにグループ分けしたデータを並び替えを行い、徐々にグループ分けの間隔を狭めて並び替える動作を繰り返すアルゴリズムです。挿入ソートの改良版で、ドナルド・シェルというアメリカの研究者が考案したためこの名前が付けられています。計算量はO(nlog n)となります。

クイックソート

クイックソートは、ある基準値をあらかじめ決めておき、それより大きな値を集めた列と小さな値を集めた列に振り分けます。その中でさらに基準値を決めて、同様の操作を繰り返すアルゴリズムです。計算量はO(nlog n)となります。

過去問 令和5年春期問7（高度試験午前Ⅰ 問3）

配列に格納されたデータ2，3，5，4，1に対して，クイックソートを用いて昇順に並べ替える。2回目の分割が終わった状態はどれか。ここで，分割は基準値より小さい値と大きい値のグループに分けるものとする。また，分割のたびに基準値はグループ内の配列の左端の値とし，グループ内の配列の値の順番は元の配列と同じとする。

ア．1，2，3，5，4
イ．1，2，5，4，3
ウ．2，3，1，4，5
エ．2，3，4，5，1

解答：ア
クイックソートは、ある基準値をあらかじめ決めておき、それより大きな値を集めた列と小さな値を集めた列に振り分けます。その中でさらに基準値を決めて、同様の操作を繰り返すアルゴリズムです。
問題文によると「分割は基準値より小さい値と大きい値のグループに分けるものとする。また，分割のたびに基準値はグループ内の配列の左端の値とし，グループ内の配列の値の順番は元の配列と同じとする」とあることから、これに従ってソートします。

元データ：[2，3，5，4，1]・・・基準2
1回目：[1，2][3，5，4]・・・基準1・基準3
2回目：[1][2][3][5，4]
よって、アが正解です。