探索と整列のアルゴリズム — なぜ「速い」アルゴリズムが必要なのか

導入

10万件のデータから目的のものを探すとき、先頭から1件ずつ見ていくのと、賢い方法で絞り込むのとでは、速さがまったく違うと思いませんか。アルゴリズムの「効率」を知ることは、プログラムの性能を左右する重要な視点です。

くわしく知ろう

アルゴリズムの効率は、データ件数 n が増えたときの処理ステップ数の増え方で評価します。この評価にはBig O記法（ビッグオー記法）が使われ、O(1)・O(log n)・O(n)・O(n log n)・O(n²)のように表記します。

探索アルゴリズムには大きく2種類があります。線形探索は配列の先頭から1件ずつ順に比較する方法で、整列されていなくても使えます。計算量はO(n)です。二分探索はソート済みの配列を前提に、中央の要素と比較して探索範囲を半分ずつ絞り込みます。計算量はO(log n)で、1024件のデータでも最大10回の比較で答えが見つかります。

整列（ソート）アルゴリズムにも複数の種類があります。バブルソートは隣り合う要素を繰り返し比較・交換する方法で、計算量はO(n²)かつ安定ソートです。選択ソートも同じくO(n²)です。挿入ソートは最良ケースO(n)、最悪O(n²)で、部分的にソート済みのデータに強いという特徴があります。

より高速なアルゴリズムとして、クイックソートとマージソートがあります。クイックソートは「分割統治法」を使い、平均O(n log n)を実現しますが、最悪ケースはO(n²)になります。マージソートは常にO(n log n)を保証したうえで安定ソートでもあり、大規模データに適しています。

具体例

たとえば電話帳で「山田」を探す場合、先頭の「あ行」から順に見ていくのが線形探索で、真ん中あたりから開くのが二分探索にあたります。一方、商品の売上ランキングを毎日更新する処理では、データ件数が多いほどO(n²)とO(n log n)の差が顕著になるため、クイックソートやマージソートが実務で使われます。

まとめ・試験ポイント

• 線形探索＝先頭から順に比較・整列不要・O(n)
• 二分探索＝ソート済み配列が前提・O(log n)・1024件なら最大10回
• バブル/選択/挿入ソート＝O(n²)・実装が簡単・小規模データ向け
• クイックソート＝平均O(n log n)・最悪O(n²)・ピボット選択が重要
• マージソート＝常にO(n log n)かつ安定ソート・大規模データに適する
• 試験では二分探索の「ソート済み前提」、マージソートの「安定性と計算量保証」、O(n log n)とO(n²)の差異が頻出