読み方のヒント

矢印ボタン(または ← → キー)でページを移動できます。

第5節 アルゴリズムと計算量

5.2 探索と整列

よく使われる探索(探す)と整列(並べ替える)のアルゴリズムの考え方を比べます。

アルゴリズム考え方前提
線形探索先頭から順に比べるなし
2分探索真ん中と比べ、半分に絞ることを繰り返す整列されている
選択ソート残りから最小を選び、先頭と入れ替えることを繰り返すなし
バブルソート隣どうしを比べ、逆なら入れ替えることを繰り返すなし
クイックソート基準の値より小さいものと大きいものに分け、それぞれを同じ方法で並べるなし

1,000件の整列された伝票の番号から探すとき、線形探索では最大1,000回、2分探索では最大10回ほど(2を10回かけると1,024)の比較で済みます。

23 / 30