このユニットでは、データの中から目的の値を見つける「探索」と、データを順番に並べ替える「整列(ソート)」の代表的なアルゴリズムを学ぶ。線形探索法・2分探索法、選択ソート・バブルソート・クイックソートを、素朴な手法から効率的な手法へと比較しながら理解する。処理の仕組みと速さ(計算量)の違いはITパスポートで頻出する重要分野である。
データの先頭から順番に1つずつ調べ、目的の値を探す最も素朴な探索法。
線形探索法は、配列やリストの先頭から末尾に向かって1つずつ値を照合し、目的のデータが見つかれば終了する方法です。逐次探索とも呼ばれます。 データが並べ替えられていなくても使える手軽さが利点ですが、データ件数が増えるほど調べる回数も増えます。最悪の場合は全件を調べることになり、n個のデータでは平均n/2回、最大n回の比較が必要です。 試験では、整列が不要な点と、後述の2分探索法より一般に遅い点が対比して問われます。データ数nに比例して時間が増える特徴を押さえましょう。
たとえ出席番号順に並んでいない名簿で、特定の人を上から一行ずつ指でなぞって探すイメージ。並び順を気にせず探せますが、人数が多いと時間がかかります。
記憶フック線形探索法といえば先頭から順に1つずつ調べる
整列済みデータの中央と比較し、範囲を半分ずつ絞り込んで探す効率的な探索法。
2分探索法(バイナリサーチ)は、あらかじめ昇順や降順に整列されたデータに対し、まん中の値と目的の値を比較し、目的の値がどちら側にあるかを判断して探索範囲を毎回半分に狭めていく方法です。 1回の比較で候補が半減するため非常に高速で、n個のデータでも比較回数はおよそlog₂n回で済みます。たとえば1000件でも約10回で見つかります。 試験では「データが整列済みであることが前提」という条件と、線形探索より圧倒的に速い点が頻出です。整列されていないデータには使えない点に注意しましょう。
たとえ辞書で単語を引くとき、まん中あたりを開いて前か後ろかを判断し、さらにその半分を開く、を繰り返すイメージ。数回めくるだけで目的のページに着きます。
記憶フック2分探索法といえば整列済みを半分ずつ絞り込む
未整列部分から最小(最大)値を選び、先頭に置くことを繰り返す整列法。
選択ソートは、データ全体から最小値(または最大値)を選び出して先頭の要素と交換し、次に残りの中から最小値を選んで2番目に置く、という操作を繰り返してデータを並べ替える方法です。 「選んで(select)所定の位置に置く」という発想が直感的で分かりやすいのが特徴です。データ件数をnとすると、比較回数はおよそn²に比例し、データが多いと遅くなります。 試験では、毎回未整列部分から最小値を探して確定させていく動作の流れが問われます。次のバブルソートとの違い(交換のしかた)を整理して覚えましょう。
たとえ背の順に並ぶとき、列全体から一番背の低い人を見つけて先頭に立たせ、次に残りで一番低い人を2番目に、と順に決めていくイメージ。
記憶フック選択ソートといえば最小値を選んで先頭に置く
隣り合う要素を比較し、大小が逆なら交換することを繰り返す基本の整列法。
バブルソートは、隣接する2つの要素を順に比較し、並び順が逆であれば入れ替える操作を端から端まで繰り返して整列する方法です。隣接交換法とも呼ばれます。 この操作を1巡すると最大値(または最小値)が端に確定し、泡(bubble)が浮かび上がるように値が移動していくことが名前の由来です。比較回数はおよそn²に比例し、件数が多いと遅くなります。 試験では、選択ソートが「最小値を選んで置く」のに対し、バブルソートは「隣同士を比較して交換する」点の違いが頻出です。動作の仕組みを取り違えないようにしましょう。
たとえ横一列に並んだ人が、隣の人と背を比べて高い方を右へずらす、を繰り返すイメージ。何巡もすると自然に背の順に整います。
記憶フックバブルソートといえば隣同士を比較して交換
基準値で大小2グループに分け、各グループを再帰的に並べ替える高速整列法。
クイックソートは、基準値(ピボット)を1つ選び、それより小さい値の組と大きい値の組にデータを振り分け、それぞれの組に同じ処理を繰り返して整列する方法です。分割統治法に基づく代表的な高速ソートです。 大きな問題を小さな部分問題に分けて解くため、平均的にはおよそn×log₂nに比例する速さで処理でき、選択ソートやバブルソートより高速です。 試験では、ピボットで分割して再帰的に処理する考え方と、n²型の素朴なソートより速い点が問われます。名前のとおり「速い」整列法として位置づけて覚えましょう。
たとえクラスを基準の身長で「それより低い人」「高い人」の2グループに分け、各グループでさらに同じ分け方を繰り返して並べていくイメージ。
記憶フッククイックソートといえば基準値で分けて分割統治
関連の過去問演習は今後のアップデートで追加予定です。