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

整列の問題になると、二重ループの中で何が起きているのか追えなくなる。

配列を並べ替えるコードを前に、手が止まっていませんか？

探索の問題は読めるようになったのに、整列になると急に難しく感じる。その感覚は正しくて、整列にはループが二つ重なるという事情があります。

私はエンジニアとして10年以上、Webシステムの開発や運用に携わってきました。実務で整列そのものを手書きすることはほとんどありませんが、並べ替えの順序を一つ取り違えたせいで、画面に出る一覧の順番が崩れる不具合には何度も立ち会ってきました。

つまり、整列は仕組みを知っておく価値がある処理です。この記事では、選択ソートを軸にして、二重ループの中身を落ち着いて追える形に整理していきます。

整列は、決めた順番に並べ替える処理¶

まず、整列が何をする処理なのかを確認しましょう。ひとことで言えば、配列の中身を決められた順番に並べ替えることです。

点数の低い順、名前のあいうえお順、日付の新しい順。どれも整列です。

処理としては地味ですが、科目Bではよく出ます。理由は単純で、配列と繰返しと条件分岐が全部入っているからです。

そこを押さえるために、まずは順番の呼び方から確認します。

昇順と降順の違いを取り違えない¶

並べ替えの向きには名前が付いています。小さい順に並べるのが昇順、大きい順に並べるのが降順です。

昇順は数が上がっていくから昇順、と覚えると迷いません。1, 3, 5, 8 のような並びです。

問題文では、昇順に整列するアルゴリズムである、という一文がさらっと書かれています。ここを読み飛ばすと、比較の向きを逆にした選択肢を選んでしまいます。

問題を開いたら、まず昇順か降順かに印を付ける。それだけで防げる失点があります。

そして、向きが変わってもコードの構造は変わりません。比較の不等号がひっくり返るだけです。

昇順で読めるようになっていれば、降順の問題が出ても慌てる必要はないということです。

整列の中心にあるのは交換処理¶

整列のコードを分解すると、やっていることは二つしかありません。値を比べることと、値を入れ替えることです。

比べるのは条件分岐、入れ替えるのが交換処理と呼ばれる部分になります。

この交換処理が、初めて見ると不思議な形をしています。次のコードを見てください。

/* data[1] と data[2] の値を入れ替える */
tmp ← data[1]
data[1] ← data[2]
data[2] ← tmp

なぜ tmp という変数がいるのか、ここが最初の関門です。

いきなり data[1] ← data[2] と書いてしまうと、data[1] に元々入っていた値が上書きされて消えます。消えてしまえば、data[2] に戻す値がもうありません。

だから、先に片方を避難させておきます。tmp は一時的な置き場所というわけです。

コップの中身を入れ替えるときに、空のコップをもう一つ用意するのと同じ発想だと思ってください。この三行は、整列の問題でほぼ必ず出てきます。

配列の添字そのものに不安が残っている場合は、先にそちらを固めておくと整列の理解が早くなります。

【関連記事】擬似言語の配列と添字がわからない人へ｜要素数・二次元配列の読み方を解説

選択ソートを一行ずつ追ってみる¶

交換処理が分かったら、いよいよ整列のコードに入ります。ここでは選択ソートを取り上げます。

選択ソートは、名前のとおり選んで並べるアルゴリズムです。未整列の範囲から最小値を選び、その範囲の先頭と交換する。これを繰り返します。

考え方が素直なので、最初の一つとして向いています。実際のコードは次のとおりです。

○selectionSort(整数型の配列: data)
  整数型: i, j, min, tmp

  for (i を 1 から data の要素数 - 1 まで 1 ずつ増やす)
    min ← i
    for (j を i + 1 から data の要素数 まで 1 ずつ増やす)
      if (data[j] < data[min])
        min ← j
      endif
    endfor
    /* 未整列部分の最小値を、その範囲の先頭と入れ替える */
    tmp ← data[i]
    data[i] ← data[min]
    data[min] ← tmp
  endfor

長く見えますが、役割で区切れば三つの部品でできています。

外側のループが並べる位置を決め、内側のループが最小値を探し、最後の三行で交換する。この構造が見えれば、あとは値を追うだけです。

変数 min は「位置」を持っている¶

ここで一つだけ注意点があります。min という変数が持っているのは、最小の値ではなく最小値がある位置です。

min ← j と書かれているとおり、代入されているのは添字のほうになります。

だから比較の条件も data[j] < data[min] という形になります。data[min] と書いて初めて、その位置にある値を取り出せるわけです。

値と位置を混同すると、この手の問題は一気に読めなくなります。min は場所を覚えている付箋のようなもの、と考えると整理しやすくなります。

トレース表で二重ループを追う¶

構造が分かったところで、実際に値を動かしてみましょう。data が {5, 3, 8, 1} の4要素だとします。

外側のループが一周するごとに、配列がどう変わるかを並べたのが次の表です。

i が2のときに注目してください。最小値がすでに正しい位置にあるので、自分自身と交換する形になり、並びは変わりません。

無駄に見えますが、コードとしてはこれで正しく動きます。ここで手が止まる人はとても多いところです。

そして i が3で終わっている点も大切です。最後の一つは、それより前がすべて確定した時点で自動的に決まるので、外側のループは要素数 - 1 で止まります。

こうして表に書き出すと、頭の中だけで追うより格段に確実になります。書き方の型を知りたい場合は、こちらの記事が役に立ちます。

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

バブルソートとの違いを整理する¶

科目Bで出てくる整列は、選択ソートだけではありません。バブルソートも定番です。

名前は違いますが、目指すところは同じです。違うのは、どうやって並べるかという段取りになります。

バブルソートは、隣り合う二つを比べて、順番が逆なら交換する。これを配列の端から端まで繰り返します。

軽い泡が水面に浮かび上がるように、大きい値が少しずつ端へ移動していくのでバブルと呼ばれます。

二つの違いを並べると、次のようになります。

問題を読むときは、いちばん下の行が役に立ちます。内側のループで位置を覚えているなら選択ソート、その場で交換しているならバブルソートです。

名前を当てること自体が目的ではありませんが、どちらか分かると先の展開が読めます。

比較の回数はどう数えるか¶

整列の問題では、比較を何回行うかを問われることがあります。ここも仕組みが分かれば計算できます。

選択ソートで4要素なら、内側のループは3回、2回、1回と回ります。合わせて6回です。

一般に要素数を n とすると、比較の回数は n から1までを足し合わせた形になり、n × (n - 1) ÷ 2 で求められます。要素数が10なら45回という具合です。

ここで気づいてほしいのは、要素数が2倍になると回数はおよそ4倍になるということ。整列は、データが増えたときの負担が大きい処理なのです。

数え方に迷ったら、内側のループが何回回るかを i ごとに書き出してみてください。3回、2回、1回と並べてから足すほうが、公式を思い出そうとするより確実です。

実務で自分でソートを書かず、用意された仕組みを使うのはこのためでもあります。とはいえ試験では、中身を知っていることが問われます。

比較して絞り込むという発想は、探索のアルゴリズムとも地続きです。合わせて読むと理解が深まります。

【関連記事】擬似言語の線形探索と二分探索の違いとは？科目Bで差がつく探索の読み方

二重ループでつまずかないための読み方¶

整列が難しく感じる最大の理由は、ループの中にループがあることです。ここだけ、読み方のコツを分けて説明します。

大事なのは、内側と外側を同時に見ないことです。

まず外側の i を一つの値に固定してしまいます。i は1、と決めたうえで、内側の j だけを最後まで動かす。内側が終わったら、外側を一つ進めてまた内側を回す。

この順番を守れば、追う対象はいつも一つだけになります。頭の中の負荷がぐっと下がるはずです。

内側のループが終わる位置を見る¶

もう一つ、見落としやすいのが内側のループの範囲です。選択ソートの内側は j を i + 1 から始めています。

なぜ i からではないのか。すでに min ← i として先頭を候補にしているので、同じ場所をもう一度比べる必要がないからです。

範囲の始まりと終わりは、問題によって微妙に変わります。1 から始まるのか、0 から始まるのか、要素数までなのか要素数 - 1 までなのか。

ここを毎回確認する習慣を付けておくと、境界だけ間違えるという失点が減ります。繰返し処理の書き方そのものを整理したい場合は、こちらもどうぞ。

【関連記事】擬似言語のwhileとforってどう違う？繰返し処理で迷子にならない方法を詳しく解説

手を動かすと、整列は一気に身近になる¶

読んで分かった気になっても、整列は自分で追わないと定着しません。とくに二重ループは、実際に値が動くところを見るのが近道です。

Giji Academy の擬似言語シミュレーターでは、整列のようなコードを一行ずつ実行しながら、配列の中身が変わっていく様子を確認できます。自分が予想した並びと実際の並びを、その場で見比べられます。

先に紙で予想を書き、それから実行する。この順番だと、ずれた場所がはっきり分かります。よかったら学習ページから試してみてください。

よくあるつまずきと直し方¶

整列の学習でつまずく場所は、ある程度決まっています。まとめて確認しておきましょう。

自分がどれに当てはまるか探しながら読んでみてください。

一番多いのは、二行目の min の取り違えです。位置なのか値なのかが曖昧なまま読み進めると、必ずどこかで詰まります。

科目Bは20問を100分で解く試験です。整列の問題に長く迷っている余裕はありません。

だからこそ、構造を先に頭に入れておくことが効いてきます。読む前から何が書いてあるか予想できていれば、確認するだけで済みます。

こうした細かい取り違えは、見直しの型を持っておくと拾えるようになります。

【関連記事】擬似言語でケアレスミスが多い人へ｜よくある間違いと確認方法

まとめ¶

整列は、比べることと入れ替えることの二つでできていました。入れ替えには tmp を使う三行の交換処理が必要です。

選択ソートは、未整列の範囲から最小値を選んで先頭と交換する処理でした。外側のループが位置を決め、内側のループが最小値を探します。

min が持っているのは値ではなく位置です。ここを押さえるだけで、コードの見え方が変わります。

バブルソートとの違いは、内側で位置を覚えているか、その場で交換しているか。問題を読むときの目印にしてください。

二重ループは、外側を固定して内側だけを追う。この読み方を身につければ、整列以外のアルゴリズムでも同じ手が使えます。

一歩ずつ配列が整っていく様子が見えるようになると、整列の問題は少し楽しくなってきます。次に問題を開いたら、まず外側のループを一周だけ追ってみてください。