探し方と並べ替え方

いちばん素直な探し方が 線形探索（逐次探索）だよ。先頭から1つずつ、見つかるまでくらべる。for で回すやり方そのままだ。

強みは前提が何も要らないこと。並んでいなくても、途中が抜けていても、とにかく端から見ていけば必ず答えが出る。

弱みは手間で、運が悪ければ最後の1個まで見ることになる。データが n 個あるとき、最悪で n 回、平均で n/2 回くらべる。

ここで大事なのは、データが2倍になれば手間も2倍という関係だよ。まっすぐ比例して伸びる。これが線形探索の「線形」だ。

2分探索 は、真ん中と1回くらべるたびに探す範囲を半分に捨てるやり方だよ。

真ん中の値を見て、探している値のほうが小さければ左半分、大きければ右半分。これを繰り返す。

ただしタダでは使えない。使うには データが昇順（または降順）に並んでいること が必要だ。並んでいないと「小さいほうは左」が成り立たないからね。ここが線形探索との決定的な違いで、試験でも必ず前提条件を聞いてくる。

手間はどうなるか。1回くらべるごとに範囲が半分になるので、n を1になるまで何回半分にできるかがそのまま比較回数になる。それを表す式が log₂ n だよ。100万件でも 2 の20乗が約104万なので、およそ20回で終わる。

3つ目は、探さずに場所を計算で出してしまうやり方だよ。キーを ハッシュ関数 に通し、出た値をそのまま置き場所（添字）として使う。これが ハッシュ探索 だ。

よく使われるのは「ある数で割った余り」。たとえばキーの各桁を足して 13 で割った余りを場所にする、といった具合だよ。

うれしいのは、データが何個あっても手間が変わらないこと。関数に1回通すだけで場所が出るので、10個でも100万個でも同じ。伸びない、という意味で手間は 1 と書く。

ただし違うキーから同じ場所が出ることがある。これが 衝突 だね。衝突が多いほど、あとから空き場所を探す手間が増えて速さが落ちる。だから理想は、ハッシュ値がどの場所にも同じ確率で散ること ―― つまり 一様分布 に近いことだよ。かたよった分布だと同じ場所ばかりが当たってしまう。

3つの探し方の手間を、n、log₂ n、1 と書いてきた。この「データが増えたときの伸び方」だけを取り出した書き方が オーダ記法 だよ。O(n) のように書く。

コツは、細かいところを気にしないこと。手間が 3n + 5 回でも O(n) と書く。定数倍の 3 も、おまけの 5 も、n が大きくなれば効かなくなるからだ。オーダが見ているのは形だけだよ。

よく出てくるのは次の5つ。

• O(1) … データが増えても変わらない（ハッシュ探索）
• O(log n) … とてもゆっくり増える（2分探索）
• O(n) … 比例して増える（線形探索）
• O(n log n) … 比例より少し急（速い整列）
• O(n²) … 急に増える（素朴な整列）

この並びは上ほど速い。試験ではこの順番さえ持っていれば、たいていの組合せ問題は消去法で片づくよ。

オーダの違いが効いてくるのは、データが増えたときだよ。数字で見ると差がはっきりする。

O(n) のやり方は、データが10倍になれば時間も10倍。素直だね。

O(n²) は、10倍のデータで 100倍。1秒で終わっていた処理が1分40秒になる。さらに10倍のデータなら1万倍で、もう待てない時間だよ。

O(log n) は逆にほとんど増えない。1000件が100万件になっても、比較回数は10回から20回になるだけだ。

ここで押さえたいのは、遅いやり方は小さいデータでは気づけないということ。手元の10件では一瞬で終わるので、本番でデータが増えて初めて表に出る。書いた時点でオーダを見積もっておくのは、そのための習慣だよ。

ここからは 整列（ソート）だよ。まずは考え方が素朴な3つから。どれも手間は O(n²) で、内側と外側で二重にループを回す形になる。

バブルソート は、隣どうしをくらべて逆なら入れ替える。これを端まで繰り返すと、小さい値が泡のように端へ寄っていく。

選択ソート は、残っている中から最小値を選び出して先頭に置く。次はそれを除いた残りから最小値を選ぶ。これを繰り返すだけだよ。

挿入ソート は、すでに並んでいる列の正しい位置に、次の1つを差し込む。トランプを手札に並べていく動きそのままだね。

3つの見分け方は「隣とくらべる＝バブル」「最小を選ぶ＝選択」「正しい位置に差す＝挿入」。試験ではこの言い回しがほぼそのまま選択肢になるよ。

O(n²) より速い、O(n log n) の並べ替えもある。共通しているのは、全部を総当たりせず、分けたり構造を使ったりするところだよ。

クイックソート は、基準値（ピボット）を1つ選び、それより小さい組と大きい組に分割する。それぞれの組の中でまた基準値を選んで分割する。この繰り返しだけで並ぶ。試験でいちばんよく出るのがこれだよ。

マージソート は、半分に割って、それぞれを並べてから合流させる。合流するときは両方の先頭をくらべて小さいほうから取るだけで済むのがポイント。

ヒープソート は、前のレッスンで出てきたヒープを使う。根に必ず最大値が来る性質があるので、根を取り出しては形を整え直す、を繰り返す。

シェルソート は挿入ソートの改良版。離れた要素どうしを先に並べておいてから、だんだん間隔を狭めていく。ざっくり整えてから細かく整えるので、挿入ソートの弱点が減るんだ。

整列にはもう1つ、速さとは別の性質がある。安定かどうかだよ。

同じ値のものが、元の並び順のまま保たれる整列を 安定な整列 と呼ぶ。

たとえば名簿を先に名前順に並べておいて、そのあと点数順に並べ替えるとしよう。安定な整列なら、点数が同じ人どうしは名前順のまま残る。安定でない整列だと、同じ点数の中で順番が入れ替わってしまうかもしれない。

安定なのは、バブルソート・挿入ソート・マージソートあたり。クイックソートやヒープソートは、離れた場所と入れ替えるので安定ではないよ。

速い整列が安定とはかぎらない。ここが覚えどころだね。

クイックソートもマージソートも「分けて、その中でまた同じことをする」だったね。これを素直に書くと、関数の中から自分自身を呼ぶ形になる。これが 再帰呼出し だよ。

定義はそれだけ ―― 関数の中で自分自身を用いた処理を行うこと。

大事なのは、必ず止まる条件を持たせることだ。f(n) が f(n-1) を呼ぶなら、いつかは n が 1 になって、そこで自分を呼ばずに値を返す。この行き止まりが無いと永久に呼び続けてしまう。

計算を追うコツは、いちばん奥まで降りてから、順に戻ってくると考えること。呼び出しの途中の状態は前のレッスンのスタックに積まれていて、帰るときに逆順で取り出されるよ。

最後に、試験で必ず並べて出される用語を整理しよう。再帰的 と名前が似ているだけで、中身はまったく別のものだよ。

• 再帰的（リカーシブ）… 自分自身を呼び出せる
• 再入可能（リエントラント）… 処理が終わる前に、別のところから呼ばれても正しく動く
• 再使用可能（リユーザブル）… 一度使ったあと、読み込み直さずにもう一度実行できる
• 再配置可能（リロケータブル）… 主記憶のどこに置いても動く

見分けの鍵は何が問われているかだよ。「自分を呼ぶ」なら再帰的、「同時に呼ばれても大丈夫」なら再入可能、「読み直さずまた使う」なら再使用可能、「置き場所を選ばない」なら再配置可能。

4つとも「再」で始まるので、選択肢に4つ並んだ瞬間に迷いやすい。後ろの2文字で切り分けよう。