マナビングITパスポート
回別一覧 →
総合トップへ

選択ソートのトレースで途中の配列を正しく読む方法

ITパスポート試験 令和8年度 問67 ／ アルゴリズムとプログラミング › アルゴリズムとプログラミング

過去問にチャレンジ

令和8年度 問67

手続sortは、要素数が2以上の整数型の配列を引数numberArrayで受け取り、その要素を昇順に並べ替えた結果を出力する。手続sortの動作確認のために、処理の途中でjの値とworkArrayの全ての要素を出力する。配列numberArrayを{3, 5, 1, 2, 4}とし、手続sortをsort(numberArray)として呼び出したとき、jの値が3と出力された直後のworkArrayの全ての要素の出力はどれか。ここで、配列の要素番号は1から始まる。 〔プログラム〕

  ○sort(整数型の配列: numberArray)
    整数型: minIndex, j, k
    整数型の配列: workArray ← numberArray  // 配列の複製を作る
    for (jを1から(workArrayの要素数－1)まで1ずつ増やす)
      // j番目から末尾までの要素の中で最も小さい値をもつ要素の要素番号を
      // 一つ求める
      minIndex ← j
      for (kを(j + 1)からworkArrayの要素数まで1ずつ増やす)
        if (workArray[k]がworkArray[minIndex]より小さい)
          minIndex ← k
        endif
      endfor
      workArray[j]とworkArray[minIndex]の値を入れ替える

      // 動作確認のために、jの値とworkArrayの全ての要素を出力する
      jの値を出力する
      workArrayの全ての要素を先頭から順にコンマ区切りで出力する
  endfor
  workArrayの全ての要素を先頭から順にコンマ区切りで出力する
令和8年度 問67の図
  1. ア

    1,2,3,4,5

  2. イ

    1,2,3,5,4

  3. ウ

    4,5,3,2,1

  4. エ

    5,4,3,2,1

解答・解説を見る

会話形式の解説

講師講師
今回は擬似言語のトレース問題です。トレースとは、プログラムを1行ずつ実際に動かしたつもりで変数の値を追うことです。注目点は、jの値と配列を出力するタイミングが、入れ替えの前なのか後なのかという点です。
受験者受験者
「昇順に並べ替える」と書いてあるので、つい1,2,3,4,5を選びたくなります。でも、途中の状態を聞かれているのですよね。
講師講師
そのとおりです。まず処理の中身を確認しましょう。j番目から末尾までの中で最も小さい値を探し、その要素番号をminIndexに入れて、j番目の要素と入れ替えます。この並べ替え方は選択ソートと呼ばれます。
受験者受験者
出力は入れ替えの後に書かれているので、jごとに入れ替えを済ませてから配列を書き出せばよいのですね。
講師講師
はい。初期状態は3,5,1,2,4です。j=1では全体の最小値を探します。どうなりますか。
受験者受験者
最小値は1で、3番目にあります。先頭の3と入れ替えて、1,5,3,2,4になります。
講師講師
正解です。続けてj=2では、2番目以降の5,3,2,4から最小値を探します。
受験者受験者
最小値は4番目の2なので、2番目の5と入れ替えて1,2,3,5,4です。
講師講師
では問題のj=3です。3番目以降は3,5,4です。
受験者受験者
最小値は3ですが、すでに3番目にあります。この場合も入れ替えは行われるのでしょうか。
講師講師
minIndexはjのまま変わらないので、3番目と3番目、つまり自分自身との入れ替えになります。配列は変わらず、1,2,3,5,4が出力されます。これが正解です。
受験者受験者
そうすると、1,2,3,4,5になるのは、4番目の5と5番目の4を入れ替える次のj=4の処理の後ということですね。
講師講師
そうです。ほかの選択肢も確認しましょう。このプログラムは先頭から順に小さい値を確定させていくので、j=1の時点で先頭は1に決まります。4で始まる4,5,3,2,1は途中経過に現れません。5,4,3,2,1は大きい順の降順で、「より小さい」値を前に移すこの手続では、途中でも最後でもこの並びにはなりません。
受験者受験者
整理すると、j回目の処理が終わると先頭からj個が昇順で確定するので、j=3の後は1,2,3までが確定していて、残りはまだ5,4のままということですね。
講師講師
よく整理できています。補足すると、完成形を選ばせるのはよくある引っかけです。途中の状態を問われたら、jごとに配列を書き出して追うのが確実です。また、このプログラムは複製したworkArrayを並べ替えるので、引数のnumberArray自体は変わりません。

まとめ

この問題は、擬似言語で書かれた選択ソートをたどり、jの値が3と出力された直後の配列を答えるものです。選択ソートでは、j番目から末尾までの最小値を探してj番目と入れ替えるので、初期状態3,5,1,2,4はj=1で1,5,3,2,4、j=2で1,2,3,5,4になります。j=3では最小値3がすでに3番目にあり、自分自身との入れ替えになるため、配列は1,2,3,5,4のまま出力されます。完全に整列した1,2,3,4,5は、次のj=4の処理の後に初めて現れます。トレース問題では、出力が入れ替えの前後どちらにあるかを確認し、jごとに配列を書き出すのが確実です。

解答・解説

正解はイです

この問題のテーマ

擬似言語で書かれた選択ソートを1ステップずつ追い、j=3の処理を終えた時点の配列の中身を答える問題です。

解き方の考え方

このプログラムは、j番目から末尾までの中で最も小さい値を探し、j番目の要素と入れ替えます。いわゆる選択ソートです。出力は入れ替えの後に行われるので、j=1、2、3の順に、最小値を探す処理と入れ替えを実際にたどります。初期状態は3,5,1,2,4です。j=1では、全体の最小値1（要素番号3）と先頭の3を入れ替えて1,5,3,2,4になります。j=2では、2番目以降の5,3,2,4の最小値2（要素番号4）と2番目の5を入れ替えて1,2,3,5,4になります。j=3では、3番目以降の3,5,4の最小値3がすでに3番目にあるため、minIndexはjのままです。自分自身と入れ替えるだけなので配列は変わらず、1,2,3,5,4が出力されます。

選択肢ごとの解説

  1. ×ア  1,2,3,4,5
    1,2,3,4,5という完全に整列した状態は、すべての処理が終わった後の結果です。j=3の時点では、4番目の5と5番目の4はまだ入れ替わっていません。この2つが入れ替わるのは、次のj=4の処理です。
  2. ○イ  1,2,3,5,4
    j=1とj=2で入れ替えが起きて1,2,3,5,4になります。j=3では未整列部分の最小値3がすでに3番目にあるので、配列は変わりません。そのため、jの値3の直後には1,2,3,5,4が出力されます。
  3. ×ウ  4,5,3,2,1
    このプログラムは、先頭から順に小さい値を決めていきます。最初のj=1の時点で先頭は1に決まるので、4で始まる4,5,3,2,1という並びは途中経過として現れません。
  4. ×エ  5,4,3,2,1
    5,4,3,2,1は大きい順（降順）の並びです。この手続は「より小さい」値を前に移して昇順に並べ替えるので、途中でも最後でもこの並びにはなりません。

補足

選択肢アの完全に整列した状態は、「最後には昇順になる」という結果だけを覚えていると選びやすい引っかけです。途中の状態を問われたら、jごとに配列を書き出して追うのが確実です。なお、このプログラムは複製したworkArrayを並べ替えるので、引数のnumberArray自体は変わりません。

POINT

  • 未整列部分から最小値を探して先頭側と入れ替える処理は、選択ソートです。
  • 選択ソートでは、j回目の処理が終わると、先頭からj個の要素が昇順に確定します。
  • 最小値がすでにj番目にある場合はminIndexがjのままなので、自分自身との入れ替えになり、配列は変わりません。
  • トレース問題では、出力が入れ替えの前にあるのか後にあるのかを必ず確認します。

※出典：令和8年度 ITパスポート試験 問67（一部改変）