アルゴリズム分野への対応と攻略ポイント

アルゴリズムには様々な種類がありますが、本項目で紹介している探索と整列アルゴリズムが最も基本です。確実に理解しておくようにしましょう。

本試験出題例

基本情報技術者 平成23年春期問題 午前：問8
※リンク先はIPAサイトの過去問（PDFファイル）になります。

整列アルゴリズムの一つであるクイックソートの記述として、適切なものはどれか。

ア　対象集合から基準となる要素を選び、これよりも大きい要素の集合と小さい要素の集合に分割する。この操作を繰り返すことで、整列を行う。
イ　対象集合から最も小さい要素を順次取り出して、整列を行う。
ウ　対象集合から要素を順次取り出し、それまでに取り出した要素の集合に順序関係を保つよう挿入して、整列を行う。
エ　隣り合う要素を比較し、逆順であれば交換して、整列を行う。

アルゴリズムとは

アルゴリズムとは、何らかの問題を解決するための手順や方式、目的の処理を実行するための手続きや解法のことです。仮に「1から1,000までの連続した数値の総和」を求めたいとすると、その計算方法は何通りか考えられるはずです。それら一つひとつがアルゴリズムなのです。

正しいアルゴリズムとは

アルゴリズムを図で表現したものがフローチャートであり、また、プログラム言語によって表したものがプログラムです。アルゴリズムは各人各様なので、これが正しいというものはありません。目的の処理が問題なく実行できればそれで良いのです。ただし、必要以上に複雑なものよりは単純なものの方が読みやすく、もし何らかの間違いが存在している場合でも発見しやすくなるためより良いのは確かです。

線型探索アルゴリズム

探索アルゴリズムとは、配列中から目的のデータを見つけ出すアルゴリズムです。その最も基本的なものが線型探索（逐次探索）アルゴリズムです。これは、探索の対象となる配列の先頭から順に探索している値と同じデータを調査していく方法です。配列数がn個である場合ならば、最大比較回数はn回（＝探索している値と同じデータが存在しなかった場合）、最小比較回数は1回（＝たまたま先頭あったデータが探索している値と一致した場合）となります。

一般的な整列アルゴリズム

複数のデータを特定の基準に基づいて整列させるための整列アルゴリズムには以下の様にいくつか種類があり、その概要は本試験においても問われる可能性が高いので、区別できるように把握しておきましょう。

●クイックソート…適当な基準値（ピボット）を選び、それより小さな値のグループと大きな値のグループにデータを分割する。同様にして、グループの中で基準値を選び、それぞれのグループを分割する。この操作を繰り返していく方法。交換法の一種。

●ヒープソート…すべての要素を順にヒープに追加したのち、最大値または最小値である根（ルート）を取り出してリストに追加する。ヒープは再構築されるため、次のルートが残りの要素中における最大値または最小値となり、これを取り出してリストに追加する処理を繰り返す方法。選択法の一種。

●シェルソート…隣り合う要素同士で交換する挿入法の効率の低さを改善するため、適当な間隔で複数のデータ列に対して挿入法を適用し、その間隔が1になるまで繰り返す。そして間隔が1に達したら最後に挿入法を実行して全体の整列を完了させる方法。挿入法の一種。

●マージソート…すでに整列済みの2つのデータ列を併合し1つにまとめる方法。まず目的のデータ列を2等分し、それぞれを整列させ、両者を併合（マージ）することで全体の整列を実現する。

解答と解説

正解：ア

大きい要素の集合と小さい要素の集合に分割するための基準となる要素を選ぶ点に特徴があるクイックソートの説明です。
イ　選択法です。
ウ　挿入法です。
エ　バブルソートです。