交換して並べる｜バブルソートと選択ソート【基本情報技術者試験科目B】

並べ替えの回です。まずすべての整列の土台になる「入れ替え」から始めて、いちばん素朴な2つ ── バブルソートと選択ソートを見ます。

期間限定クーポンPR｜Udemy の講座科目B オリジナル模試 3回分・60問42%OFF 1,500円~~2,600円~~中身を見る ›

この回の内容を動画で見る

講義「並べ替え（交換・挿入）」（全8分49秒）です。

入れ替えには、作業用の変数が1つ要る
バブルソート ── 隣どうしを比べる
選択ソート ── いちばん小さいものを選ぶ
つまずきポイントまとめ
次に読む

入れ替えには、作業用の変数が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

なぜ3行要るのか

a[1] ← a[2] と書いた瞬間、a[1] にあった値は消えます。そのあと a[2] ← a[1] と書いても、コピーされるのはさっき上書きした値です。

結果、両方とも同じ値になります。だから先に退避させます。

この3行は、交換して並べる整列に出てきます。

日本語で1行で書かれることもある

実際の出題では、この3行を data[i]とdata[j]の値を入れ替える と日本語1行で書くことがあります（令和5年度問3）。

やっていることは同じです。作業用の変数は、書かれていないだけで中にあります。

バブルソート ── 隣どうしを比べる

バブルソートの特徴

やること隣どうしを比べて、順が逆なら入れ替える

1周でわかることその範囲でいちばん大きいものが右端まで運ばれる

確定するのは右から1つずつ

交換の回数順が逆のたびに入れ替えるので多い

先頭から隣どうしを比べて、順が逆なら入れ替える。それを端まで続けます。

バブルソート ── 1周目

整数型の配列: a ← {5, 3, 8, 1}　／　隣どうしを比べて、順が逆なら入れ替える

j ＝ 1：a[1] ＞ a[2]　5 ＞ 3 なので入れ替える

j ＝ 2：a[2] ＞ a[3]　5 ＞ 8 ではないので、そのまま

j ＝ 3：a[3] ＞ a[4]　8 ＞ 1 なので入れ替える

1周おわり

いちばん大きい 8 が右端に決まった。次の周からは見ない

3回比べて、2回入れ替えた。1周で「いちばん大きいもの」が右端まで運ばれる

矢印が入れ替えたペアです。3回比べて、2回入れ替えました。1周終わると、いちばん大きい 8 が右端に決まります。

あとは同じことを、確定した右端を除いてくり返すだけです。

周が進むと、比べる範囲が縮む

灰色は確定ずみ。もう見ない

はじめ

内側の j は 1〜3 を比べる（上限 aの要素数－ i ＝ 3）

1周目のあと

j は 1〜2 を比べる（上限 2）

2周目のあと

j は 1 だけ（上限 1）

3周目のあと

全部が確定した

内側の上限 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 を経由する理由は、最初の節で見たとおりです。

図「周が進むと、比べる範囲が縮む」と、内側の上限の対応

i ＝ 14 － 1 ＝ 3　→　j は 1〜3

i ＝ 24 － 2 ＝ 2　→　j は 1〜2

i ＝ 34 － 3 ＝ 1　→　j は 1 だけ

バブルソートを1行ずつ動かす

当サイトオリジナルの例題

ループ開始前

配列

▲ いま読んでいる▲ いま書いた

いま計算していること

まだ計算していません

変数の状態

トレース表（進めると1行ずつ積み上がります）

選択ソート ── いちばん小さいものを選ぶ

選択ソートの特徴

やること残りの中からいちばん小さいものを探して、先頭と交換

1周でわかることその範囲の最小が左端に決まる

確定するのは左から1つずつ

交換の回数1周に1回だけ。位置を覚えておいて最後に交換

もう1つが、残っている中からいちばん小さいものを探して、先頭と入れ替えるやり方です。

選択ソート ── 1周目

整数型の配列: a ← {5, 3, 8, 1}　／　いちばん小さいものを探して、先頭と入れ替える

min ← i　まず、いまの先頭を仮の最小に

min は 1（値ではなく位置を覚える）

j ＝ 2：a[2] ＜ a[min]　3 ＜ 5 なので min ← 2

j ＝ 3：a[3] ＜ a[min]　8 ＜ 3 ではないので、そのまま

j ＝ 4：a[4] ＜ a[min]　1 ＜ 3 なので min ← 4

内側はここで終わり。min は 4

内側が終わってから、交換の3行

a[1] と a[min] を入れ替える。1周に1回だけ

見つけても、その場では入れ替えない。位置を覚えておいて、最後に1回

バブルとの違いは交換の回数です。もっと小さいものを見つけてもその場では入れ替えず、いちばん小さいものの位置だけ覚えておいて、最後に1回だけ交換します。探すところは A2-2 の「仮の王者」と同じです。

こちらも、確定したところは次から見ません。ただし確定は左から伸びます。

確定は、左から伸びる

灰色は確定ずみ。バブルとは逆に、左から増える

はじめ

内側の j は 2〜4 を探す（下限 i ＋ 1 ＝ 2）

1周目のあと

j は 3〜4 を探す（下限 3）

2周目のあと

j は 4 だけ（下限 4）

3周目のあと

全部が確定した

内側の下限 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行ずつ積み上がります）

試験での見分け方

内側のくり返しの中に交換の3行があればバブル、外側にあれば選択です。入れ替えの行がどこにあるかを見れば、どちらか分かります。

つまずきポイントまとめ

まちがえ方	正しい読み方
入れ替えを2行で書く	作業用の変数が要る。3行
バブルの内側を毎周同じ回数まわす	右から確定するので1周ごとに減る
選択で見つけるたびに交換する	位置だけ覚えて、1周に1回交換
選択の内側を 1 から回す	確定済みの左は見ない。`i ＋ 1` から
どちらか見分けられない	交換の3行がどこにあるかを見る

次に読む

A5-2	挿入ソート ─ 手札を並べるのと同じ
A4-2	文字列照合 ─ 重ねて、ずらして、また重ねる
G9-2	2重ループ ─ 内側と外側の回り方
目次	基本情報技術者試験科目B 攻略ガイド