ITパスポート 令和8年度 問67：algorithmに関する問題

答えは b です。

このプログラムは「一番小さい数を見つけて前に持ってくる」を順番にくり返して、小さい順に並べ替えています。

{3,5,1,2,4} から始めると、1回目で1を、2回目で2を前に出し、3回目（jが3のとき）まで進むと「1,2,3」までが確定し、残りはまだ「5,4」のまま。だからこの瞬間の並びは 1,2,3,5,4 です。

👉 覚え方：左から1個ずつ“最小”を確定させていく並べ替え。

ほかの選択肢：a 1,2,3,4,5は全部終わった後／c・d は大きい順で、このプログラムの動きと合いません。

なぜこれが正解か

正解は b。このプログラムは選択ソート（昇順）。各回で「未確定範囲の最小値」を探し、その範囲の先頭と交換する。{3,5,1,2,4}で追跡する。

• j=1：範囲[1〜5]の最小は1（位置3）。先頭と交換 → 1,5,3,2,4
• j=2：範囲[2〜5]の最小は2（位置4）。交換 → 1,2,3,5,4
• j=3：範囲[3〜5]の最小は3（位置3、自分自身）。交換なし → 1,2,3,5,4

よってj=3出力直後は 1,2,3,5,4。

各選択肢の解説

• a 1,2,3,4,5：完全に整列後（最終結果）で、j=3時点ではまだ。
• c 4,5,3,2,1／d 5,4,3,2,1：降順で本手続の動きと不一致。

覚え方・ひっかけ注意

選択ソートは「左からj個が確定済み」。jの出力直後は先頭j個だけ整列、残りは未整列のまま。最終形（a）と途中経過を混同しないこと。

理論的背景

本問は選択ソート（Selection Sort）アルゴリズムのトレース問題である。選択ソートは「未ソート部分の最小値を見つけ、未ソート先頭要素と交換する」操作をN-1回繰り返すアルゴリズムで、計算量はO(N²)（最良・平均・最悪すべて同じ）。

プログラムのトレース（初期配列{3, 5, 1, 2, 4}）：

• j=1：k=2〜5でworkArray[k]<workArray[minIndex]を検索。minIndex=1（値3）→k=2(5≥3)→k=3(1<3,minIndex=3)→k=4(2≥1)→k=5(4≥1)。minIndex=3。workArray[1]と[3]を交換→{1, 5, 3, 2, 4}。出力：j=1, {1,5,3,2,4}
• j=2：minIndex=2（値5）→k=3(3<5,minIndex=3)→k=4(2<3,minIndex=4)→k=5(4≥2)。minIndex=4。workArray[2]と[4]を交換→{1, 2, 3, 5, 4}。出力：j=2, {1,2,3,5,4}
• j=3：minIndex=3（値3）→k=4(5≥3)→k=5(4≥3)。minIndex=3。workArray[3]と[3]を交換（自己交換）→{1, 2, 3, 5, 4}。出力：j=3, {1,2,3,5,4}

j=3直後の配列は{1, 2, 3, 5, 4}→正解b「1, 2, 3, 5, 4」。

実務での使われ方

選択ソートは実装の単純さから教育目的で重要なアルゴリズムだが、実際のソフトウェア開発では大規模データに対してO(N²)の計算量は実用的でない。実務ではTimSort（PythonのsortedやJavaのCollections.sort）・QuickSort・MergeSort等のO(N log N)アルゴリズムが使われる。特にTimSort（Timsort：ランダムデータに近いO(N log N)・ほぼソート済みデータにO(N)）はPython・Java・Rubyの標準ライブラリのデフォルトソートアルゴリズムとして採用されている。

アルゴリズムトレース能力は実務でも重要であり、バグ発見・コードレビュー・パフォーマンスチューニングでプログラムの実行フローを手動で追う能力が求められる。特に分散システム・データパイプラインのデバッグでは複雑なステートマシンをトレースする能力が差別化スキルとなる。

試験での位置づけ

アルゴリズムトレース問題はITパスポートのテクノロジー系「アルゴリズム」分野で出題頻度が高く、ソートアルゴリズム（バブルソート・選択ソート・挿入ソート）のトレースが頻出。本問のような疑似コード読解では「配列のインデックスは1始まりか0始まりか」「ループの境界条件」「swap操作の順序」の3点が正解を左右するポイント。本問では配列要素番号が1から始まる（1-indexed）ことに注意。2022年以降のITパスポート試験では探索アルゴリズム（線形探索・二分探索）・再帰呼び出し・スタック・キューのトレースも出題されている。基本情報技術者試験ではより複雑なアルゴリズム（動的計画法・グラフアルゴリズム）の実装トレースや計算量（O記法）の分析問題まで出題範囲が拡大する。

選択肢の発展補足

j=3直後の状態で選択肢aの{1,2,3,4,5}（完全ソート済み）と誤答するケースは「j=3でソートが完了している」という誤解から生じる。選択ソートのj=3ステップはindex 3の位置（4番目の要素）に正しい値を配置するステップであり、4番目(5)と5番目(4)の交換がまだ行われていない。j=4で初めて{1,2,3,4,5}のソート完了状態になる。選択肢c{4,5,3,2,1}・d{5,4,3,2,1}は逆順ソートをイメージした誤答で、選択ソートが「最大値を後ろに移動する」バブルソートと混同された場合に起きうる誤り。バブルソート・選択ソート・挿入ソートの3アルゴリズムの動作原理の違い（バブル：隣接要素比較交換/選択：最小値選択して先頭と交換/挿入：整列済み部分に適切位置を挿入）を整理しておくと本問のようなトレース問題で迷いが生じなくなる。