選択ソート選択ソートは、最小値の要素を選択して、先頭の要素と置き換える整列アルゴリズムで、基本選択法ともいいます。例:「1・5・7・3・9」の5枚のカードを選択ソートで昇順に並び替える。要素[1]~[5]の値を調べて、最小値を求める。1.で求めた最小値を先頭の要素と交換する。残りの要素について、1と2を繰り返す。挿入ソート挿入ソートは、前の方の整列済みの並びの途中へ、直後の要素を挿入する整列アルゴリズムで、基本挿入法ともいいます。例:「1・5・7・3・9」の5枚のカードを挿入ソートで昇順に並び替える。先頭の要素を1要素だけの整列済みの並びと見立てる。整列済みの並びの要素と、その直後の要素を比較して、バブルソートと同じ要領で並び替えを行う。最後の要素を処理するまで、2を繰り返す。マージソートマージソートは、並びを2等分しながら、分割された部分同士を併合(マージ)することによって、全体を整列させるアルゴリズムです。例:「2・7・5・3・8・1・4・6」の8枚のカードをマージソートで昇順に並び替える。並びを2等分することを、整列済みの部分並びが見つかるまで反復する。(要素が1つになれば整列済みとみなすので、反復は必ず終了する。)整列済みの部分並び同士を、整列状態を保つように併合して、1つの部分並びにする。全体が1つの部分並びになるまで、2を反復する。シェルソートシェルソートは、シェル氏によって考案された挿入ソートの改良版の整列アルゴリズムです。適当な間隔を決めて、等間隔の飛び飛びの要素で作った部分的な並びに対して挿入ソートを適用する。間隔を狭めながら、間隔が1になるまで1を繰り返す。例:「2・7・5・3・8・1・4・6」の8枚のカードをシェルソートで昇順に並び替える。挿入ソートは、元々の並びが整列状態に近いほど高速になる性質があるため、間隔を空けて部分的な並びを作って徐々に整列させることで速度の向上を図っています。クイックソートクイックソートはその名の通り、特に高速な整列アルゴリズムです。適当な基準値を定めて、その値より小さい要素を前の方に移し、その値以上の要素を後の方へ移す。分割したそれぞれのグループへ、1の処理を反復して、全てのグループに属する要素数が1になるまで繰り返す。例:「9・2・7・5・3・8・1・4・6」の9枚のカードをクイックソートで昇順に並び替える。反復する毎に、分割されたグループの数は2倍、4倍、8倍というペースで増えていくので、各グループに含まれる要素の数は急激に減っていきます。基準値と要素の値を比較する回数が急速に減っていくことが、クイックソートが特に高速である理由です。ヒープソートヒープソートは、ヒープを経由する整列アルゴリズムです。ヒープは「小さい山」という意味の言葉であり、親の値が必ず子の値以上であることを保つ二分木です。要素の並びを元にして、ヒープを構築します。子の処理には、木構造アルゴリズムの一種である、ヒープ構築アルゴリズムを用います。根に当たる要素を取り出して、並びの端へ移します。ヒープに残った要素に対して、ヒープ再構築アルゴリズムを適用します。2と3をヒープの要素がなくなるまで繰り返します。例:「2・7・5・3・1・4・6」の7枚のカードをヒープソートで降順に並び替える。二分木は木の階層ごとに、部分木の数が2倍、4倍、8倍と増えていきます。値の大小比較の回数は2つの部分木の根を比較するだけなので、ヒープソートは特に高速とされています。アルゴリズムを理解する。再帰的アルゴリズムの考え方、特徴、実現に適したデータ構造を理解する。配列などに格納されたデータの集まりから、特定のデータを探すことです。その値が見つかる場合と、見つからない場合があり、複数ある場合には最初の一つを見つければ良い場合と、全てを見つける必要がある場合があります。探索の結果も見つかったかどうかだけではなく、何番目に見つかったか、いくつあったか、という情報を帰す場合があります。線形探索法(リニアサーチ)線形探索法とは、配列の先頭から1つずつ調べてゆき、求めるデータが見つかるか、又は配列の最後まで探し終わったとき探索を終了する方法です。以下に、線形探索法の場合の流れ図を示します。ここでは、4つの数が入った配列の中から、「5」を探すものとします。表示して探索を終了、最後まで探して見つからなかった場合は、「無し」と表示して終了します。簡単にするために、配列の最後に「番兵」と呼ばれるデータを追加する方法があります。探すデータと同じ値を、配列の最後尾の次に追加しておくことで、反復の終了条件として、添字の範囲を毎回チェックする必要がなくなります。整列済みのデータの並びを二等分しながら、目的のデータを探す探索アルゴリズムです。昇順に整列済みの配列であれば、以下のような流れとなります。並び全体の中央のデータと目的のデータを比較する。目的のデータが中央のデータより小さければ、前半の部分並びにを対象にして、大きければ後半の部分並びを対象にして、1を繰り返す。最終的に部分並びの要素が1つになったら、見つからなかったことになる。要素の数が65,536個(216)であった場合、線形探索法なら、最大で65,536回、平均でも32,768回かかります。減っていき、最大でも17回で済みますので、二分探索法の方がはるかに高速なアルゴリズムです。ハッシュ表探索ハッシュ表探索法は、データの格納位置をデータの値から決めることで、目的のデータを直接得られる方法です。ハッシュ表という配列の複数の要素に、探索対象の部分並びを所属させておき、目的のデータの値に対してある種の計算を行い、一つの部分並びだけを探索対象として選択する探索アルゴリズムです。目的のデータを100で割った余りは、必ず0~99の数になります。この値を100個の要素の配列の索引として、一つの部分並びを選択することが出来ます。この例の「目的のデータを100で割った余り」といったような、目的のデータを範囲内の値に換算する関数のことを「ハッシュ関数」といいます。ハッシュ表探索では、最初の1回目の検索で多くの部分並びの中から1つを選択することで、初めの時期の検索回数を減らしています。ハッシュ関数と衝突ハッシュ関数を適用した結果、値が重複してしまうことを衝突(シノニム)といいます。ハッシュ表を使う場合、ハッシュ関数を検討する際に極力シノニムが発生しないようにすることも重要ですが、余りハッシュ表を大きくすると無駄も多いので、シノニム発生時の対処法もあわせて検討しておく必要があります。データの件数が1万件だからといって、1万件のハッシュ表を作るのでは、メモリをムダに消費してしまいます。シノニム対策としては、以下のようなパターンが主流です。ハッシュ表の隣接する要素を使う。シノニム用の領域を別途用意する。併合のアルゴリズム併合のアルゴリズムは、二つの整列済みのデータの並びを一つの整列されたデータの並びにするアルゴリズムです。二つの配列のそれぞれ先頭の要素を比較して、値の小さい要素を併合先の配列の先頭に移す。残りの配列について、それぞれの配列の最後の要素を移し終わるまで1の処理を繰り返す。再帰のアルゴリズム(リカーシブ)再帰とは、定義自身の一部にその定義が含まれるという性質です。再帰のアルゴリズムは、反復を含むアルゴリズムと似ていますが、それよりも簡潔になります。値として「1」を返す。この関数を使って、1から4までの和を計算する場合、以下のように再帰が進行していきます。4+f(3)=4+3+f(2)=4+3+2+f(1)=4+3+2+1=10再帰のアルゴリズムは、これまでに紹介した整列や探索のアルゴリズム(マージソート、クイックソート、二分探索法)でも活用されているアルゴリズムです。応用情報グラフのアルゴリズムを理解する。(木構造の場合は、結線のことを枝とも呼ぶ)これらのグラフを扱うアルゴリズムをグラフのアルゴリズムといいます。木の巡回法(再掲)木構造からデータを探して読み出すことを「木の巡回」といいます。二分木の巡回法には幅優先探索と深さ優先探索があります。階層が浅いデータを優先して検索する方法です。幅優先探索を行うと、最初に子のデータを読み出します。子のデータが検索したデータでない場合は、1階層目の節や葉のデータを左から右へと順番に読み出していきます。1階層目のデータが検索したデータでない場合は、次は2階層目と進んでいく、という方法です。深さ優先探索は、左部分木を優先して、階層が下のデータを先に読み出す方法です。順番で読み出す方法です。右の図を例にとって説明すると、最初の節である根のデータ1を読み出し、次に左部分木の節のデータ2を読み出します。その次は2階層目の左部分木のデータ3を読み出します。順番で読み出す方法です。右の図を例にとって説明すると。根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。次に、上の階層に戻ってデータ2を読み出します。その次に2階層目の右部分木のデータ3を読み出します。順番で読み出す方法です。右の図を例にとって説明すると、根から始めて2階層目の左部分木で左部分旗がなくなるので、データ1を読み出します。次は2階層目の右部分木のデータ2を読み出します。その次は、上の階層に戻ってデータ3を読み出します。グラフのある出発点の節から終着点の節へ到達するのに、結線ごとに要する時間や距離の合計が最短である結線の並びです。この最短経路をたどることを「最短経路探索」といいます。結線ごとに要する時間や距離を総称して「コスト」といいます。例:ダイクストラのアルゴリズム出発点から各説へのコストの表は、出発点の節だけゼロとし、それ以外の節へのコストは初期値として無限大とする。出発点の節から、結線の一つをたどって、節のデータを調べる。その節へのコストの記録が、今回の経路のコストより大きいなら、今回の経路のほうが短いので、今回の経路のコストを記録し、直前の節の記号をその節に関するデータとして記録する。(その節へのコストが初期値の無限大だったのなら必ずこちらの処理)その節へのコストの記録が、今回の経路のコスト以下なら、今回の結線は最短経路に含まれないので、それ以降の処理対象から除外する印を記録する。以上の処理を、処理していない結線について反復する。すべての処理が終わったら、終着点の節から最短のコストを回答する。直前の節を次々と逆行して、出発点から終着点までの節の順序を経路として回答する。アルゴリズムを理解する。用語例:文字列照合、KMP法(クヌース・モリス・プラット法)、BM法(ボイヤ・ムーア法)文字列処理のアルゴリズム文字列処理のアルゴリズムは、一連の文字の並びを処理するアルゴリズムです。一つの文字列の後へ別の文字列を追加して、一つの文字列にします。文字列の途中に別の文字列を挿入して、一つの文字列にします。文字列の一部の文字を取り除いて、残りを一連の文字列にします。文字列の先頭の文字から、特定の文字列を一文字ずつ照合する。すべての文字が一致したら、全体の処理を終了して対象の文字列の位置を返す。対象の文字列の1文字後ろから1の処理を反復する。対象の文字列の最後を越えたら、探索失敗として終了する。ボイヤ・ムーア法(BM法)ボイヤとムーアによって考案された、高速の文字列照合アルゴリズムです。特定の文字列の後尾から前の方へ照合することと、一致しない場合には、複数の文字をスキップすることが特徴です。特定の文字列を前処理して、「特定の文字が何文字目に出現するかを表す表」「一致した文字のパターンと、その場合にスキップしていい文字数を対応付ける表」の2表を作成する。対象の文字列の先頭部分を特定の文字列の後尾から前方向へ、文字の比較をすすめる。一致したら全体の処理を終了して、対象の文字列の位置を返す。一致しなかったら、比較時に得られた情報と1で作った表を元にして、文字をスキップし、2の処理に戻る。コントロールブレイク処理、編集処理のアルゴリズムを理解する。ファイル処理のアルゴリズムファイル処理とは、入力装置や外部記憶装置から読み取ったファイルを処理することです。処理対象のデータが主記憶装置の中にないため、以下のような手順が基本となります。ファイルを開き、内容を主記憶装置の中に展開します。開いたファイルに対して、1レコードずつ所定の処理を行います。ここでいうファイルは以下の定義となります。同じフィールドを持つレコードの集まりファイルの性質として、データ件数が膨大になることがあるため、ハードディスクなどの外部記憶装置に作業ファイルを作成し、中間結果を一時退避しながら処理をすすめることもある。十分な空き容量が必要となる。ファイルの併合処理ファイルの併合処理は、二つの整列済みのレコードの並びで構成されるファイルを、一つの整列されたレコードのファイルにする処理です。ファイルA、B、Cをそれぞれ開く。ファイルA、Bを1レコードずつ読み込み、値の小さい方のレコードをファイルCに出力し、出力した方のファイルの次のレコードを読み込む。これを両ファイルの終端まで繰り返す。ファイルA、B、Cをそれぞれ閉じる。コントロールブレイク処理コントロールブレイクとは、同じキー値を持つレコード軍の切れ目のことです。コントロールブレイク処理とは、コントロールブレイクに出会ったらそのレコード群の処理を終了し、複数のレコード群の処理を反復することです。レコード群の中のレコードごとの処理の反復とあわせて、二重の反復になります。部署が同じである間、社員毎の給与を計算用変数に加算していく。部署名と計算用変数の値を中間ファイルに出力し、計算用変数0で初期化。2と3をファイルの終端まで繰り返す。ファイル終端まで来たら、部署名と計算用変数の値を中間ファイルに出力。中間ファイルの内容を処理の最終結果として書き出す。ファイルの編集処理ファイルの編集処理は、既存のファイルのデータを修正する処理です。マスターファイルM、トランザクションファイルT、新マスターファイルNを開く。ファイルMとファイルTからから1レコードずつ読み込み、キー値を比較して以下の処理を行う。これをファイル終端まで繰り返す。Tのキー値=Mのキー値なら、ファイルTのレコードをファイルNに出力し、ファイルMとファイルTの次のレコードを読み込む。(データの更新)Tのキー値>Mのキー値なら、ファイルMのレコードをファイルNに出力し、ファイルMの次のレコードを読み込む。Tのキー値<Mのキー値なら、ファイルTのレコードをファイルNに出力し、ファイルTの次のレコードを読み込む。ファイルM、ファイルT、ファイルNを閉じる。応用情報アルゴリズムは、擬似言語、流れ図、決定表(デシジョンテーブル)などを用いて表現することを理解する。アルゴリズムの設計方法を理解する。用語例:再帰、分割統治法アルゴリズム設計アルゴリズムとは、目的にたどり着くための道筋や処理の手順のことです。アルゴリズムを考える、設計する目的は、単に問題を解く方法を見つけるだけではなく、より効率的に、より速く、より簡単に問題を解くアルゴリズムを探す事が重要です。同じ結果を出すための処理であっても、そのアルゴリズムが異なると、処理にかかる時間や、必要となるメモリの容量などが異なってきます。効率の良いアルゴリズムほど、処理時間が短くなり、メモリの消費量が少なく済むものなのです。アルゴリズムの表現プログラムを設計するときには、アルゴリズムを何らかの形式で表現します。人間が用いる自然言語とプログラム言語を混合した言語です。アルゴリズムをできるだけ人間向きに自然言語で表現しつつ、反復や選択のように微妙な部分にプログラム言語を混用したりします。プログラム言語と同様にテキストエディタで描くことが出来、図形を用いた表現に比べて修正が容易なのが特徴です。分野では、以下のような簡易な図記号を混用したものを擬似言語と称しています。使われたものを紹介します。決定表(デシジョンテーブル)決定表(デシジョンテーブル)は、条件とその条件に対する処理の関係を4つの部分からなる表にして表現する技法です。問題を処理するための条件を表します。条件によって取りうる行動を表します。条件表題欄の各条件について、当てはまる場合は[Y]、当てはまらない場合は[N]と記載します。条件判断を必要としない場合は[-]と記載します。行動表題欄の各行動について、当てはまる場合に[X]と記載します。当てはまらない場合は空欄か[-]と記載します。大きなプログラムの場合、「行動」の単位で「サブルーチン」化することがよく行われています。大きな問題を小さな問題に分割して、それぞれの問題ごとに解決に集中する方法です。再帰のアルゴリズム、モジュール分割、オブジェクト指向設計などが分割統治法の具体的な例です。ソートのアルゴリズムの中でも、マージソートやクイックソートは分割統治法に基づいて設計がなされています。