【ＡＰ３問】ソートと探索法とオーダー（応用情報技術者試験）

このNoteでは、応用情報技術者試験から「ソートと探索法」を計算する問題を搔き集めました。令和7年～元年のたった3問ですが。

問題数のわりに覚えることが多いです。ソートや探索の手順・入替/探索の回数やオーダーを、ソート6種・探索3種について覚えるのは大変です。

それでは始めましょう！

＞【ＡＰ３問】確率と期待値は全ての中核
＞【ＡＰ７問】期待値と目安時間

講座 | ソート

※昇順を前提。降順の場合は比較や最大値を探すなど読み替えて下さい。ただしヒープソートは除きます。

• バブルソート（隣接交換法）：隣同士で比べて入れ替える、を先頭から繰り返し行う。値が1個ずつずれていくのが特徴

• 基本選択法（単純選択法）：未整列部分から最小値を探し、現在の位置と入れ替える（昇順の場合）。

• 基本挿入法（単純挿入法）：対象を整列済み部分の適切な位置に挿入していくことで、順に整列を進める。

• クイックソート：基準値を選び、基準値より小さいグループと大きいグループに分け、また基準値を選び～を繰り返し、整列を進める。

• ヒープソート：ヒープ木を作って根（最大値）を取り、再度ヒープ木を構成し直すを繰り返す。

• マージソート：データを分割していき、各部分をソートしながら併合していく。

こういうのは、図解で過程を見た方が良いです。＞合格教本（amazon検索結果）