科目Bのソート問題を解くコツ｜交換される値を追ってみよう

ソートの問題になると、途中で何がどこへ行ったのか分からなくなる。

配列の中身が入れ替わった瞬間に、目で追うのをあきらめていませんか？

科目Bのソート問題は、擬似言語の中でも手強い部類です。値が動くうえに、動く場所が毎周変わるからです。

でも大丈夫です。ソート問題には決まった読み方があって、そこさえ押さえれば、あとは同じ作業の繰り返しになります。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務で並べ替えを自分で書く機会はほとんどありませんが、値の入れ替わりを頭の中だけで追おうとして間違える人は、新人でもベテランでも見かけます。

つまり、追えなくなるのは実力の問題ではありません。追い方を決めていないだけです。

この記事では、問題文の読み方から答え合わせまでを5つの段に分けてお伝えします。科目Bの全体像から確かめたい人は、先に親記事を読んでおくと理解が早くなります。

【関連記事】基本情報技術者試験の科目Bとは？擬似言語・アルゴリズム対策を初心者向けに解説

科目Bのソート問題は何を聞いているのか¶

まず、この分野で何が問われるのかをはっきりさせておきましょう。

意外に思うかもしれませんが、並べ替えが終わった後の配列を答えさせる問題は多くありません。聞かれるのは、たいてい途中の状態です。

出題のされ方を整理すると、次の4つに収まります。

表を見て分かるとおり、どれも途中経過を見ていないと答えられません。ここがソート問題の本質です。

並べ替えの結果より、途中の状態を聞かれる¶

結果だけなら、小さい順に並べればいいので考える必要がありません。だから試験は途中を聞いてきます。

言い換えれば、ソート問題は整列の知識を試しているのではなく、コードを1行ずつ追えるかを試しています。

追う力さえあれば解けるので、身構えなくて大丈夫です。

アルゴリズムの名前は覚えなくていい¶

バブルソート、選択ソート、挿入ソート。名前を覚えようとして疲れてしまう人がいます。

けれど科目Bの問題文に、アルゴリズムの名前が書かれていないことは珍しくありません。目の前のコードが何をしているかを読み取るほうが、はるかに実戦的です。

名前より、比べる場所と入れ替える場所がどこかを見てください。それが分かれば、名前を知らなくても最後まで追えます。

整列アルゴリズムそのものの書き方をもう一度確認したい場合は、文法側の記事が用意してあります。

【関連記事】擬似言語の整列（ソート）がわからない人へ｜選択ソートと交換処理の読み方を解説

段1：どの並べ替えが動いているのかを見分ける¶

問題文を読み終えたら、いきなり1行目から追い始めないでください。先にコードの形を眺めます。

ソート問題のコードは、二重ループになっていることがほとんどです。まずはその二重ループの内側で何を比べているかだけを見ます。

例として、値を小さい順に並べ替える擬似言語のコードを見てみましょう。出題形式に合わせた自作の例です。

○整列(整数型の配列: data)
  整数型: i, j, tmp
  for (i を 1 から data の要素数 - 1 まで 1 ずつ増やす)
    for (j を 1 から data の要素数 - i まで 1 ずつ増やす)
      if (data[j] > data[j + 1])
        tmp ← data[j]
        data[j] ← data[j + 1]
        data[j + 1] ← tmp
      endif
    endfor
  endfor

隣どうしを比べて、大きいほうを右へ送っています。これが分かれば、あとは何周目に何が起きるかを追うだけです。

二重ループなら内側が比べる側¶

外側のループは周回数を数えているだけで、値を動かしません。動かしているのは内側です。

だから最初に読むのは内側のループと、その中のif文になります。外側は後回しで構いません。

内側の終わりが data の要素数 - i のように外側の変数で決まっているときは、周を追うごとに比べる範囲が狭くなります。ここは設問でよく狙われる部分です。

繰返しの読み方そのものが不安な場合は、こちらの記事で回数の追い方を先に固めておくと楽になります。

【関連記事】科目Bの繰返し問題が解けない人へ｜ループ回数を追うコツ

比べる相手が隣か、離れた場所かで型が変わる¶

比べている2つの添字を見てください。data[j] と data[j + 1] なら隣どうしです。

一方、data[i] と data[j] のように離れた位置を比べているなら、最小値を探して先頭に持ってくる型になります。

どちらなのかを最初に決めておくと、途中で混乱しません。

段2：まず目を付けるのは交換の3行¶

コードの形が分かったら、次に見るのは値が入れ替わる場所です。ここが唯一、配列の中身が変わる瞬間になります。

擬似言語の交換は、ほぼ決まった3行で書かれます。読む順番を固定しておきましょう。

この3か所を先に押さえておけば、トレース中に迷いません。

一時変数が出てきたら交換だと決めていい¶

tmp や work のような変数が1つだけ宣言されていたら、それは値の退避用です。交換以外の用途はまずありません。

見つけた時点で交換だと判断して先に進んで構いません。判断が速くなるぶん、トレースに時間を回せます。

実務のコードでも、一時変数を1つ挟んで入れ替える書き方は今でも普通に見かけます。試験専用の書き方ではないので、覚えておいて損はありません。

ifの条件の向きで昇順か降順かが決まる¶

data[j] > data[j + 1] なら、左が大きいときに入れ替えるので小さい順に並びます。不等号が逆なら大きい順です。

ここを読み飛ばすと、正解と真逆の選択肢を選んでしまいます。条件の向きは指を置いて確かめてください。

段3：交換のたびに配列を1行ずつ書く¶

ここからが本番です。ソート問題は、頭の中だけで追うと必ずどこかで崩れます。

書くのは1周ぶんの表です。交換が起きたときだけ、配列の状態を1行足していきます。

data が {5, 3, 8, 1} だとして、1周目を追ってみましょう。

1周が終わった時点で、いちばん大きい8が右端に決まりました。これが隣どうしを比べる型の特徴です。

2周目は右端を除いた3つだけを見ればよく、比べる回数が1つ減ります。この減り方に気づけると、周回数を数える設問にも強くなります。

トレース表の作り方そのものを丁寧に確認したい人は、こちらの記事も参考になります。

【関連記事】擬似言語のトレース表の書き方｜科目Bで変数の値を追う手順を解説

1周終わりで区切り線を引く¶

表を書くとき、外側のループが1周するたびに横線を引いてください。どこまで確定したかが目で分かります。

科目Bは2周目や3周目の状態を聞いてくることが多いので、区切りがあるだけで答えを探す時間が短くなります。

交換が1回も起きない周が来たら、そこで並び終わっている¶

追っている途中で、1周まわしても交換が一度も起きないことがあります。これは、すでに全部並んでいる合図です。

この性質を知っていると、残りの周を書かずに答えを出せます。時間の節約になるので、頭の片隅に置いておいてください。

ただし、コードの側に途中で止まる仕組みが書かれていない限り、ループ自体は最後まで回ります。設問が交換回数を聞いているのか、周回数を聞いているのかは、そのつど確かめましょう。

全部書かず、規則が見えたら止める¶

要素が8個ある問題で全周を書くと、時間が足りません。2周ぶん書けば、たいてい規則が見えてきます。

右端から順に確定していく、あるいは左端から順に決まっていく。その規則さえつかめば、残りは計算で埋められます。

配列の添字そのものが苦手な場合は、配列問題の解き方をまとめた記事から先に読むのがおすすめです。

【関連記事】科目Bの配列問題の解き方｜添字を表にして追う方法

段4：まぎらわしい選択肢の見分け方¶

ソート問題の選択肢は、正解のすぐ隣に間違いが置かれています。1周ずれた配列や、交換回数を1つ多く数えた値が並びます。

よくある外し方を知っておくと、迷ったときに戻る場所が分かります。

表のいちばん下が特に多い間違いです。内側ループの上限が毎周変わることを忘れると、最後の1つが並ばないまま答えを出してしまいます。

選択肢を眺めて迷ったときは、自分の表に戻ってください。表に書いていない値が選択肢にあるなら、それは追い方のどこかがずれた証拠です。

空欄補充なら、選択肢を1つずつ交換の3行に入れる¶

空欄が交換の途中にある問題では、悩むより手を動かすほうが速く済みます。選択肢を実際に当てはめて、1周だけ追ってください。

正しくない選択肢を入れると、退避した値が上書きされて同じ数字が2つ並びます。この崩れ方が出たらすぐ切れます。

空欄補充の型に慣れておきたい人は、専用の記事も用意してあります。

【関連記事】基本情報技術者試験の科目Bの空欄補充問題の解き方を解説｜擬似言語で見る判断ポイント

段5：シミュレーターで動かして答え合わせをする¶

最後の段は、自分のトレースが合っていたかを確かめる作業です。ここを飛ばすと、間違った追い方が癖になってしまいます。

Giji Academy の擬似言語シミュレーターでは、いま見たような整列のコードを1行ずつ実行して、配列の中身が変わる様子を画面で確かめられます。無料で使えるので、紙に書いた表と見比べてみてください。

擬似言語シミュレーターで整列のコードを動かしてみる

自分の表と画面の値がずれた行が、あなたの弱点そのものです。そこだけ重点的に直せば、次の問題から精度が上がります。

ずれた行が見つかったら、その1行だけ書き直す¶

全部やり直す必要はありません。ずれた場所の前後3行を見れば、原因はたいてい添字の読み違いか、条件の向きです。

原因が分かったら、同じ型の問題をもう1問だけ解いてみてください。1問で定着します。

まとめ¶

科目Bのソート問題は、覚える量が多い分野ではありません。追い方を決めているかどうかで差がつく分野です。

今日お伝えした流れを、もう一度振り返っておきましょう。

この5段は、ソート以外の擬似言語問題にもそのまま使えます。値が動く場所を先に見つけて、動いた瞬間だけ書き留める。やっていることは同じです。

最初は表を書くのが面倒に感じるかもしれません。それでも3問も解けば、書く量が自然と減っていきます。

値の動きが目で見えるようになれば、ソート問題は得点源に変わります。今日のうちに1問、表を書きながら解いてみてください。

一度その感覚をつかめば、初めて見るコードでも落ち着いて追えるようになります。焦らず、1行ずつでいきましょう。