テクノロジ系:アルゴリズムとプログラミング

探索と整列(ソート)アルゴリズム

たとえ話

辞書を引く(2分探索)のと、1ページずつ探す(線形探索)の違い。

押さえること

• 線形探索: 先頭から順に探す。2分探索: 整列済みのデータの真ん中と比べて、半分ずつに絞る(整列が前提)
• 整列: バブルソート(隣同士を入れ替え)、選択ソート(最小を選んで先頭へ)、挿入ソート、クイックソート(平均的に高速)
• 計算量O(n)とO(log n): データが増えたとき、処理時間がどれだけ増えるかの目安。O(log n)のほうが増え方が緩やか

試験でのポイント

• 2分探索は、データが整列されていることが条件

確認問題

2分探索を使うための条件は?

関連する単元

• 流れ図・擬似言語のトレース

単元一覧へ / AIを先生にして学ぶ