並べ替えの回です。まずすべての整列の土台になる「入れ替え」から始めて、いちばん素朴な2つ ── バブルソートと選択ソートを見ます。
第2部 定番処理の型 全27回
A1-1トレース表の書き方A1-2繰返しのトレースA1-3配列のトレースA2-1配列を全部見るA2-2最大・最小を見つけるA2-3探す（線形探索）A2-4入れる・消すA2-52つの配列を突き合わせるA3-12次元配列の走査A3-22次元配列の集計A4-1文字列を1文字ずつA4-2文字列照合A5-1交換して並べるA5-2挿入ソートA6分割して並べるA7-12分探索A7-2ハッシュ表探索A8-1再帰とはA8-2再帰のトレースA9スタックとキューA10-1リストを読むA10-2リストの挿入と削除A11木構造A12木の巡回A13グラフA14AI・データを題材にしたプログラムA15ファイル処理
入れ替えには、置き場所が1つ要る
a ← {5, 3} があるとします。これを {3, 5} にしたい。つまり a[1] の 5 と a[2] の 3 を入れ替えたい。
ところが、いきなり写すと壊れます。だから tmp という空の箱を1つ用意して、3手で動かします。
入れ替えには、置き場所が1つ要る
整数型の配列: a ← {5, 3} ／ a[1] と a[2] を入れ替えたい
はじめ
a[1]5
a[2]3
tmpー
tmp は空のまま。ここへ避難させる
① tmp ← a[1]
a[1]5
a[2]3
tmp5
a[1] の 5 を tmp へ写す。a[1] はまだ 5 のまま
② a[1] ← a[2]
a[1]3
a[2]3
tmp5
a[1] が 3 で上書きされた。もとの 5 は tmp にある
③ a[2] ← tmp
a[1]3
a[2]5
tmp5
tmp の 5 を a[2] へ戻す
先に避難させてから、上書きする
整数型の配列: a ← {5, 3}
整数型: tmp
tmp ← a[1]
a[1] ← a[2]
a[2] ← tmp
a[1] ← a[2] と書いた瞬間、a[1] にあった値は消えます。そのあと a[2] ← a[1] と書いても、写るのはさっき上書きした値です。
結果、両方とも同じ値になります。だから先に避難させます。
この3行は、整列のどの方法でも出てきます。まとめて1つの手続にしてある問題も多いので、swap のような名前を見たらこれだと思ってください。
実際の出題では、この3行を data[i]とdata[j]の値を入れ替える と日本語1行で書くことがあります（令和5年度 問3）。
やっていることは同じです。避難用の箱は、書かれていないだけで中にあります。
バブルソート ── 隣どうしを比べる
バブルソートの特徴
やること隣どうしを比べて、順が逆なら入れ替える
1周でわかることその範囲でいちばん大きいものが右端まで運ばれる
確定するのは右から1つずつ
交換の回数比べるたびに起きるので多い
見分け方交換の3行が内側のくり返しの中にある
先頭から隣どうしを比べて、順が逆なら入れ替える。それを端まで続けます。
バブルソート ── 1周目
整数型の配列: a ← {5, 3, 8, 1} ／ 隣どうしを比べて、順が逆なら入れ替える
j ＝ 1：a[1] ＞ a[2] 5 ＞ 3 なので入れ替える
13
25
38
41
j ＝ 2：a[2] ＞ a[3] 5 ＞ 8 ではないので、そのまま
13
25
38
41
j ＝ 3：a[3] ＞ a[4] 8 ＞ 1 なので入れ替える
13
25
31
48
1周おわり
13
25
31
48
いちばん大きい 8 が右端に決まった。次の周からは見ない
3回比べて、2回入れ替えた。1周で「いちばん大きいもの」が右端まで運ばれる
矢印が入れ替えたペアです。3回比べて、2回入れ替えました。1周終わると、いちばん大きい 8 が右端に決まります。
あとは同じことを、確定した右端を除いてくり返すだけです。
周が進むと、比べる範囲が縮む
灰色は確定ずみ。もう見ない
はじめ
15
23
38
41
内側の j は 1〜3 を比べる（上限 aの要素数 － i ＝ 3）
1周目のあと
13
25
31
48
j は 1〜2 を比べる（上限 2）
2周目のあと
13
21
35
48
j は 1 だけ（上限 1）
3周目のあと
11
23
35
48
全部が確定した
内側の上限 aの要素数 － i は、この縮みのこと
周が進むごとに、比べる範囲が1つずつ縮みます。
1周まわすと、その範囲でいちばん大きいものが必ず右端まで運ばれます。隣と比べて大きいほうを右へ送り続けるので、いちばん大きいものは止まる場所が無いからです。
右端に来たものより大きいものは、もう残っていません。だから次の周で見ても、絶対に動きません。見るだけ無駄なので、範囲から外します。
整数型の配列: a ← {5, 3, 8, 1}
整数型: i, j, tmp
for (i を 1 から aの要素数 － 1 まで 1 ずつ増やす)
for (j を 1 から aの要素数 － i まで 1 ずつ増やす)
if (a[j] ＞ a[j ＋ 1])
tmp ← a[j]
a[j] ← a[j ＋ 1]
a[j ＋ 1] ← tmp
endif
endfor
endfor
上から読む
-
整数型の配列: a ← {5, 3, 8, 1} 整数型: i, j, tmp材料。並べ替える配列a、番号を入れておくiとj、そして入れ替えの置き場所tmpです。 -
for (i を 1 から aの要素数 － 1 まで 1 ずつ増やす)
外側＝何周目か。4個なら 1〜3 の3周です（最後の1つは自動的に決まるので回りません）。 -
for (j を 1 から aの要素数 － i まで 1 ずつ増やす)
内側＝どこまで比べるか。上限がaの要素数 － i。i が増えるほど短くなります。 -
if (a[j] ＞ a[j ＋ 1])
入れ替えの合図。隣どうしa[j]とa[j ＋ 1]を比べます。 -
tmp ← a[j] a[j] ← a[j ＋ 1] a[j ＋ 1] ← tmp endif endfor endfor入れ替える3行。合図が成り立ったときだけ動きます。tmpを経由する理由は、この節の最初に見たとおりです。
バブルソートを1行ずつ動かす
当サイトオリジナルの例題
ループ開始前
配列
いま計算していること
変数の状態
出力
トレース表（進めると1行ずつ積み上がります）
上の図と、この式の対応
i ＝ 14 － 1 ＝ 3 → j は 1〜3
i ＝ 24 － 2 ＝ 2 → j は 1〜2
i ＝ 34 － 3 ＝ 1 → j は 1 だけ
選択ソート ── いちばん小さいものを選ぶ
選択ソートの特徴
やること残りの中からいちばん小さいものを探して、先頭と交換
1周でわかることその範囲の最小が左端に決まる
確定するのは左から1つずつ
交換の回数1周に1回だけ。位置を覚えておいて最後に交換
見分け方交換の3行が内側のくり返しの外にある
もう1つが、残っている中からいちばん小さいものを探して、先頭と入れ替えるやり方です。
選択ソート ── 1周目
整数型の配列: a ← {5, 3, 8, 1} ／ いちばん小さいものを探して、先頭と入れ替える
min ← i まず、いまの先頭を仮の最小に
15
23
38
41
min は 1（値ではなく位置を覚える）
j ＝ 2：a[2] ＜ a[min] 3 ＜ 5 なので min ← 2
15
23
38
41
j ＝ 3：a[3] ＜ a[min] 8 ＜ 3 ではないので、そのまま
15
23
38
41
j ＝ 4：a[4] ＜ a[min] 1 ＜ 3 なので min ← 4
15
23
38
41
内側はここで終わり。min は 4
内側が終わってから、交換の3行
11
23
38
45
a[1] と a[min] を入れ替える。1周に1回だけ
比べるたびに入れ替えない。位置を覚えておいて、最後に1回
バブルとの違いは交換の回数です。比べるたびに入れ替えるのではなく、いちばん小さいものの位置だけ覚えておいて、最後に1回だけ交換します。探すところは A2-2 の「仮の王者」と同じです。
こちらも、確定したところは次から見ません。ただし確定は左から伸びます。
確定は、左から伸びる
灰色は確定ずみ。バブルとは逆に、左から増える
はじめ
15
23
38
41
内側の j は 2〜4 を探す（下限 i ＋ 1 ＝ 2）
1周目のあと
11
23
38
45
j は 3〜4 を探す（下限 3）
2周目のあと
11
23
38
45
j は 4 だけ（下限 4）
3周目のあと
11
23
35
48
全部が確定した
内側の下限 i ＋ 1 は、この伸びのこと
整数型の配列: a ← {5, 3, 8, 1}
整数型: i, j, min, tmp
for (i を 1 から aの要素数 － 1 まで 1 ずつ増やす)
min ← i
for (j を i ＋ 1 から aの要素数 まで 1 ずつ増やす)
if (a[j] ＜ a[min])
min ← j
endif
endfor
tmp ← a[i]
a[i] ← a[min]
a[min] ← tmp
endfor
上から読む
-
整数型の配列: a ← {5, 3, 8, 1} 整数型: i, j, min, tmp材料。バブルとの違いはminが増えたところ。いちばん小さい札の「位置」を覚えておく箱です。 -
for (i を 1 から aの要素数 － 1 まで 1 ずつ増やす) min ← i
周のはじめに、仮の最小を置く。まだ何も見ていないので、いまの先頭を仮の最小とします。 -
for (j を i ＋ 1 から aの要素数 まで 1 ずつ増やす)
内側はi ＋ 1から。確定ずみの左は見ないので、下限がずれていきます。 -
if (a[j] ＜ a[min]) min ← j endif endfor位置を覚えるだけ。もっと小さいものが見つかっても、ここでは入れ替えません。番号をminに控えるだけです。 -
tmp ← a[i] a[i] ← a[min] a[min] ← tmp endfor
内側が終わってから、交換の3行。だから1周に1回だけ動きます。ここがバブルとのいちばんの違いです。
選択ソートを1行ずつ動かす
当サイトオリジナルの例題
ループ開始前
配列
いま計算していること
変数の状態
出力
トレース表（進めると1行ずつ積み上がります）
2つのちがい
バブル比べるたびに交換する。交換が多い。確定するのは右から
選択位置だけ覚えて1周に1回交換。確定するのは左から
内側のくり返しの中に交換の3行があればバブル、外側にあれば選択です。tmp が出てくる場所を見れば、どちらか分かります。
つまずきポイントまとめ
| まちがえ方 | 正しい読み方 |
|---|---|
| 入れ替えを2行で書く | 避難用の箱が要る。3行 |
| バブルの内側を毎周同じ回数まわす | 右から確定するので1周ごとに減る |
| 選択で見つけるたびに交換する | 位置だけ覚えて、1周に1回交換 |
| 選択の内側を 1 から回す | 確定済みの左は見ない。i ＋ 1 から |
| どちらか見分けられない | 交換の3行がどこにあるかを見る |
次に読む
この記事で引用した資料
いずれも独立行政法人情報処理推進機構（IPA）が公表したものです。IPAは公表済みの試験問題について、教育目的での使用に許諾および使用料を不要としていますが、著作権は放棄していません。本記事では問題文を改変せずに引用しています。
本文の例題は当サイトのオリジナルです。
