探索と整列のアルゴリズム

線形探索法は、データの先頭から順に 1 つずつ 目的の値と比べ、一致した時点で終える探索法である。

データが並べ替えられていなくても、そのまま使える。比較回数は目的の値の位置で決まり、末尾にある場合や見つからない場合は全件と比べることになる。平均すると、およそ件数の半分の回数の比較が要る。

たとえ背表紙の並びがばらばらの本棚で、目当ての本を左端から 1 冊ずつ確かめていくようなもの。

覚え方「線形」は一本の線。線をなぞるように、端から一方向へ進む。

この用語の過去問 1 題 線形探索法 →

2分探索法は、値の小さい順 (昇順) か大きい順 (降順) に並んだ整列済みのデータで、探索範囲の 中央 の値と比べて目的の値がある側へ範囲を半分ずつ絞る探索法である。

昇順の場合、目的の値が中央の値より小さければ前半、大きければ後半だけを残し、一致するか範囲がなくなるまで繰り返す。1 回の比較で候補が約半分になるので、件数が 2 倍になっても比較は 1 回ほどしか増えない。ただし比較回数は探す値の位置でも変わり、先頭近くの値なら線形探索法の方が少ない回数で見つかることもある。

たとえ番号順に重ねた受付票の束から真ん中の 1 枚を抜き、目当ての番号が前か後ろかを決めて、残った半分でまた真ん中を見るようなもの。

覚え方「2分」は 2 つに分けること。英語の binary search の binary も「2 つの」を表す。

この用語の過去問 1 題 2分探索法 →

選択ソートは、まだ並べ終えていない範囲から 最小値 (または最大値) を選び、その範囲の端の値と交換することを繰り返す整列法である。

整列とは、データを値の大小の順に並べ替える処理である。未整列の範囲を一通り調べて端の 1 か所の値を確定させる一回りを 1 巡といい、1 巡ごとに範囲が 1 つずつ狭まる。比較回数はおよそ件数の 2 乗に比例するので、件数が多いと時間がかかる。

たとえトランプの手札で、まだ並べていない札の中から一番小さい札を探し、並べ終えた札のすぐ右へ移すことを繰り返すようなもの。

覚え方英語の selection は「選び出す」。代表選考のように、全員を見比べてから 1 人を選ぶ。

この用語の過去問 2 題 選択ソート →

バブルソートは、隣り合う 2 つの値を比べて順序が逆なら入れ替えることを、端から端まで繰り返す整列法である。

昇順に並べる場合、1 巡すると最も大きい値が末尾まで運ばれて確定する。次の巡は確定した末尾を除いた範囲で同じことを行い、1 巡の間に入れ替えが起きなければ並び終わっている。比較回数は選択ソートと同じく、およそ件数の 2 乗に比例する。

たとえ一列に並んだ人が隣の人とだけ背比べをして、背の高い方が右へ 1 つずれることを列の端まで続けるようなもの。

覚え方bubble は泡。大きな値が泡のように 1 つずつ端へ浮かび上がっていく。

この用語の過去問 1 題 バブルソート →

クイックソートは、基準値 (ピボット) を 1 つ決めてデータをそれより小さい組と大きい組に分け、各組にも同じ手順を繰り返す整列法である。

組の要素が 1 個以下になれば分ける必要がなくなり、各組を順に並べると全体が整列する。このように、同じ手順をより小さな部分に当てはめていくやり方を再帰という。平均的な比較回数は件数の 2 乗型の方法より少ないが、基準値の選び方が悪いと件数の 2 乗に近づく。

たとえ書類の山を基準の日付より前の山と後の山に分け、それぞれの山をまた同じように分けていくようなもの。

覚え方quick は英語で「速い」の意味。