コンテンツへスキップ
Topos Uranos
日本語

探索とソート

要約

探索とソートは、コレクションについての二つの基本的な問題であり、両者の間にはトレードオフがある。ソートには一度コストがかかるが、その後の探索を一回ごとに安くする。このレッスンでは線形探索と二分探索を手で書く。二分探索は、ソート済みのデータについて各段階で半分を捨てる。二分探索を不変条件によって正当化し、停止することを証明し、周回数を数え、それを台なしにする三つの誤りを調べる。続いて選択ソートと挿入ソートを、それぞれの不変条件と比較回数の正確な数え上げとともに扱い、そのあと同じ問題を範囲ライブラリで解き、探索の前にソートすべきときを決める計算を行う。

学習目標

  1. 線形探索と二分探索を実装し、二分探索を不変条件（「値があるなら、それは low と high の間にある」）によって、停止することの証明とともに正当化する。
  2. 選択ソートと挿入ソートを実装し、それぞれの不変条件を述べ、最良の場合と最悪の場合の比較回数を数える。
  3. 適切な場面で、自作の版の代わりに std::ranges::sort、std::ranges::contains、std::ranges::find、std::ranges::binary_search、std::ranges::lower_bound を、その事前条件を守って使う。
  4. 予定される探索の回数に応じて、データを探索する前にソートすべきかどうかを決め、その判断を比較回数の数え上げによって正当化する。

線形探索

探索とは、コレクションと値が与えられたとき、その値があるかどうか、あるならどこにあるかに答えることである。データの順序について何も情報がなければ、一つずつ見ていくほかに方法はない。これが線形探索である。値がないとき、このコースでは values.size() を返す。これはベクターに属さない最初の位置であり、有効な添字ではないので答えと取り違えることがない。また、第 5 節で見るように、ライブラリが従っているのと同じ約束でもある。

C++ のプログラム
#include <cstddef>#include <print>#include <vector>​// 事前条件：なし。// 事後条件：values[i] == target となる最小の添字 i を返す。// target がなければ values.size() を返す。std::size_t linearSearch(const std::vector<int>& values, int target){    // 不変条件：target は values[0], ..., values[i - 1] の中にない。    for (std::size_t i{0}; i < values.size(); ++i) {        if (values[i] == target) {            return i;        }    }    return values.size();}​int main(){    const std::vector<int> codes{405, 112, 318, 207, 112, 530};    for (const int target : {207, 112, 999}) {        const std::size_t pos{linearSearch(codes, target)};        if (pos == codes.size()) {            std::println("{}：見つからない", target);        } else {            std::println("{}：位置 {}", target, pos);        }    }}
出力
207：位置 3112：位置 1999：見つからない

正しさを保証するのは 10 行目の不変条件である。始めに i が 0 のとき、不変条件は空の部分について何かを主張しているので真である。ある周の始めに成り立ち、values[i] が探している値でなければ、その周の終わりには要素が一つ増えた形で成り立つ。さて、ループには出口が二つある。return i; が実行されるなら、values[i] は探している値であり、不変条件によりそれより前の要素はどれもそうではなかったので、i は最初の出現位置である（だから二回現れる 112 は位置 1 と報告される）。条件によってループが終わるなら、i は values.size() に等しく、不変条件は値がどこにもないことを示す。ループの中の return は関数を終わらせ、それとともにループも終わらせるので、フラグが要らなくなる。

コストは、レッスン アルゴリズムのコスト の意味で、比較 values[i] == target によって測る。値がなければ、比較はちょうど nn 回、要素ごとに一回行われる。これが最悪の場合である。値が位置 pp にあれば、p+1p + 1 回行われる。したがって線形探索は O(n)O(n) である。データが二倍になれば、仕事も二倍になる。追加の情報がなければ、これ以上よくはできない。ある要素を見ずに済ませるアルゴリズムは、値がそこにあったかどうかを知りえないからである。