整列アルゴリズム

イントロ

流れを順番に追う

基本情報技術者試験で扱う「整列アルゴリズム」を、IT知識なしでも意味と使いどころから学べるように整理します。まず目的をつかみ、似た言葉や条件の違いを短く見分けます。

定義

とは、未整列部分から最小値などを選び順に確定する整列方法です。
見分けるポイント: は、入力サイズに応じて必要な時間や記憶量を表す尺度です。は、同じ型の要素を添字で指定できるよう順に並べた構造です。は、列を分割し、整列しながら併合する整列方法です。は、隣接要素を比較交換し大きい値などを端へ送る整列方法です。は、要素を整列済み部分の適切な位置へ挿入する整列方法です。

手順

構造図

図では、整列アルゴリズムの流れを順に整理しています。入力、処理、判断、結果のつながりを確認します。

例

場面: 5個の数列を選択ソートで並べ、各回で最小値が確定する様子を見る例
順に考えると: まず選択ソートが何を表すかを確認します。次にバブルソートとの違いを、問題文の対象・条件・順序から分けます。ここでは比較して交換する型か、分割して併合する型かを見る。この順で読むと、初見の選択肢でも中心の考え方から外れた説明を除外しやすくなります。
ここが結論: この例では、比較して交換する型か、分割して併合する型かを見ることが要点です。答えを選ぶときは、すべてのソートは隣同士を交換するものだと思うという読み違いを避けます。

注意

確認

Q1

整列アルゴリズムを問題で読むとき、最も適切な見方はどれですか。

まとめ