第4部　三大馬鹿ソート

第4部　三大馬鹿ソート

このワークの目標

このワークでは、次の3つの基本的なソートを扱います。

1. バブルソート
2. 選択ソート
3. 挿入ソート

授業では、仕組みが単純で、無駄な比較や交換も多いこの3つを「三大馬鹿ソート」と呼びます。

最初から疑似言語を暗記するのではなく、次の順番で進めます。

自分の手で並べ替える
        ↓
1回の比較や交換を言葉にする
        ↓
必要な位置や回数に名前を付ける
        ↓
IPA疑似言語で書く

このワークでは、配列の要素番号は 0から始まるものとします。

data[0]  data[1]  data[2]  ...

2つの値の交換は、次のように書きます。

swap(data[a], data[b])

まずは、交換に使う一時変数の処理を省略し、どの2要素を交換するかに注目します。

1．3つのソートの違い

3つとも小さい順に並べられますが、「どの2つを比較するか」と「どこが確定するか」が違います。

2．バブルソート

2-1．まず手で動かしてみよう

バブルソートは、左端から隣り合う2つを比較します。

[6][2] 5 1 4 3
swap(6, 2)
 2  6  5 1 4 3

左の値が右の値より大きいときだけ交換します。次は、一つ右に進んで 6 と 5 を比較します。

図1　バブルソートは隣り合う2つを比較する

右端まで比較すると1周です。1周すると、その時点で最も大きい値が右端へ移動します。

2-2．1周目をトレースしよう

次の数列について、比較する2つを [ ] で囲み、必要なら交換しよう。

7 3 6 1 5 2 4

比較1：[ ][ ] _ _ _ _ _
交換後：_  _  _ _ _ _ _

比較2：_ [ ][ ] _ _ _ _
交換後：_  _  _  _ _ _ _

比較3：_ _ [ ][ ] _ _ _
交換後：_ _  _  _  _ _ _

比較4：_ _ _ [ ][ ] _ _
交換後：_ _ _  _  _  _ _

比較5：_ _ _ _ [ ][ ] _
交換後：_ _ _ _  _  _  _

比較6：_ _ _ _ _ [ ][ ]
交換後：_ _ _ _ _  _  _

[7][3] 6 1 5 2 4
swap(7, 3)
 3  7  6 1 5 2 4

 3 [7][6] 1 5 2 4
swap(7, 6)
 3  6  7  1 5 2 4

 3 6 [7][1] 5 2 4
swap(7, 1)
 3 6  1  7  5 2 4

 3 6 1 [7][5] 2 4
swap(7, 5)
 3 6 1  5  7  2 4

 3 6 1 5 [7][2] 4
swap(7, 2)
 3 6 1 5  2  7  4

 3 6 1 5 2 [7][4]
swap(7, 4)
 3 6 1 5 2  4  7

2-3．最後までトレースしよう

同じ数列について、各周が終わった時点の配列を書こう。

最初   7 3 6 1 5 2 4

1周目  3 6 1 5 2 4 7

2周目  3 1 5 2 4 6 7

3周目  1 3 2 4 5 6 7

4周目  1 2 3 4 5 6 7

5周目  1 2 3 4 5 6 7

6周目  1 2 3 4 5 6 7

2-4．日本語の穴を埋めよう

① 配列の左端から、右方向へ順番に調べる。

② 一度に比較するのは、隣り合った ＿＿ 個の値である。

③ 左の値が右の値より ＿＿＿＿ とき、2つの値を交換する。

④ 1回の比較が終わったら、比較位置を右へ ＿＿ 個分進める。

⑤ 右端まで調べたら、1周終了する。

⑥ 1周だけでは並び終わらないので、同じ処理を何周も繰り返す。

② 2個
③ 大きいとき
④ 1個分

2-5．位置に名前を付けよう

1周の中で、左側の比較位置を i とします。

data[0] と data[1]
data[1] と data[2]
data[2] と data[3]

したがって、隣り合う2つは次のように表せます。

data[＿＿] と data[＿＿＿＿]

何周目かを表す変数は j とします。要素数を n とすると、この単純なバブルソートでは、j と i はどちらも0から n － 2 まで変化します。

2-6．疑似言語の穴を埋めよう

○bubbleSort(整数型の配列: data)
    整数型: n ← dataの要素数
    整数型: i, j

    for (j を ＿＿ から ＿＿＿＿ まで 1 ずつ増やす)
        for (i を ＿＿ から ＿＿＿＿ まで 1 ずつ増やす)
            if (＿＿＿＿＿＿＿＿ ＞ ＿＿＿＿＿＿＿＿)
                swap(＿＿＿＿＿＿＿＿, ＿＿＿＿＿＿＿＿)
            endif
        endfor
    endfor

○bubbleSort(整数型の配列: data)
    整数型: n ← dataの要素数
    整数型: i, j

    for (j を 0 から n － 2 まで 1 ずつ増やす)
        for (i を 0 から n － 2 まで 1 ずつ増やす)
            if (data[i] ＞ data[i ＋ 1])
                swap(data[i], data[i ＋ 1])
            endif
        endfor
    endfor

3．選択ソート

3-1．まず手で動かしてみよう

選択ソートは、未確定部分の中から最小値を選び、未確定部分の左端と交換します。

[6] 2 5 [1] 4 3
swap(6, 1)
 1  2 5  6  4 3

図2　選択ソートは左端と最小値を交換する

この交換で、左端の 1 の位置が確定します。次は、1 を除いた未確定部分から最小値を探します。

3-2．最後までトレースしよう

次の数列を選択ソートで並べ替えよう。

7 3 6 1 5 2 4

最初
 7 3 6 1 5 2 4

位置0を確定：最小値1は位置3
[7] 3 6 [1] 5 2 4
swap(7, 1)
 1  3 6  7  5 2 4

位置1を確定：最小値2は位置5
 1 [3] 6 7 5 [2] 4
swap(3, 2)
 1  2  6 7 5  3  4

位置2を確定：最小値3は位置5
 1 2 [6] 7 5 [3] 4
swap(6, 3)
 1 2  3  7 5  6  4

位置3を確定：最小値4は位置6
 1 2 3 [7] 5 6 [4]
swap(7, 4)
 1 2 3  4  5 6  7

位置4を確定：最小値5は位置4
交換なし
 1 2 3 4 5 6 7

位置5を確定：最小値6は位置5
交換なし
 1 2 3 4 5 6 7

3-3．日本語の穴を埋めよう

① 左側には、すでに位置が確定した値が並んでいる。

② まだ確定していない部分の中から、一番 ＿＿＿＿ 値を探す。

③ 一番小さい値を見つけたら、値がある ＿＿＿＿ を覚えておく。

④ 探し終わったら、最小値と未確定部分の一番 ＿＿ の値を交換する。

⑤ 交換後、確定済みの個数を ＿＿ 増やす。

② 小さい
③ 位置
④ 左
⑤ 1

3-4．必要な情報に名前を付けよう

探し始める前は、未確定部分の左端を最小値候補にします。

minPos ← ＿＿＿＿＿＿

その次の位置から、配列の最後まで調べます。

for (i を ＿＿＿＿＿＿＿＿ から ＿＿＿＿＿＿ まで 1 ずつ増やす)

3-5．疑似言語の穴を埋めよう

○selectionSort(整数型の配列: data)
    整数型: n ← dataの要素数
    整数型: fixedCount, i, minPos

    fixedCount ← ＿＿

    while (fixedCount ＜ ＿＿＿＿＿＿)
        minPos ← ＿＿＿＿＿＿＿＿

        for (i を ＿＿＿＿＿＿＿＿ から ＿＿＿＿＿＿ まで 1 ずつ増やす)
            if (＿＿＿＿＿＿＿＿ ＜ ＿＿＿＿＿＿＿＿)
                minPos ← ＿＿
            endif
        endfor

        if (＿＿＿＿＿＿＿＿ ≠ ＿＿＿＿＿＿＿＿)
            swap(＿＿＿＿＿＿＿＿, ＿＿＿＿＿＿＿＿)
        endif

        fixedCount ← fixedCount ＋ ＿＿
    endwhile

○selectionSort(整数型の配列: data)
    整数型: n ← dataの要素数
    整数型: fixedCount, i, minPos

    fixedCount ← 0

    while (fixedCount ＜ n － 1)
        minPos ← fixedCount

        for (i を fixedCount ＋ 1 から n － 1 まで 1 ずつ増やす)
            if (data[i] ＜ data[minPos])
                minPos ← i
            endif
        endfor

        if (minPos ≠ fixedCount)
            swap(data[fixedCount], data[minPos])
        endif

        fixedCount ← fixedCount ＋ 1
    endwhile

4．挿入ソート

4-1．まず手で動かしてみよう

挿入ソートでは、左側を整列済みの部分と考えます。次の値を左隣と比較し、左隣の方が大きければ交換します。

 2 5 [6][1] 4 3
swap(6, 1)
 2 5  1  6  4 3

 2 [5][1] 6 4 3
swap(5, 1)
 2  1  5  6 4 3

[2][1] 5 6 4 3
swap(2, 1)
 1  2  5 6 4 3

図3　挿入ソートは左隣との交換を繰り返す

このワークでは、値を一時的に退避してシフトする方法ではなく、左隣との swap を繰り返す方法で考えます。

4-2．最後までトレースしよう

次の数列を挿入ソートで並べ替えよう。最初は、左端の 7 だけが整列済みです。

7 | 3 6 1 5 2 4

最初
7 | 3 6 1 5 2 4

3を挿入
[7][3] 6 1 5 2 4 → swap
 3  7 | 6 1 5 2 4

6を挿入
3 [7][6] 1 5 2 4 → swap
3  6  7 | 1 5 2 4

1を挿入
3 6 [7][1] 5 2 4 → swap
3 [6][1] 7 5 2 4 → swap
[3][1] 6 7 5 2 4 → swap
 1  3  6 7 | 5 2 4

5を挿入
1 3 6 [7][5] 2 4 → swap
1 3 [6][5] 7 2 4 → swap
1 3  5  6 7 | 2 4

2を挿入
1 3 5 6 [7][2] 4 → swap
1 3 5 [6][2] 7 4 → swap
1 3 [5][2] 6 7 4 → swap
1 [3][2] 5 6 7 4 → swap
1  2  3 5 6 7 | 4

4を挿入
1 2 3 5 6 [7][4] → swap
1 2 3 5 [6][4] 7 → swap
1 2 3 [5][4] 6 7 → swap
1 2 3  4  5 6 7

4-3．日本語の穴を埋めよう

① 左から整列済みの個数だけ、小さい順に並んでいるものとする。

② 次に処理するのは、整列済み部分のすぐ ＿＿ にある値である。

③ その値と、すぐ ＿＿ の値を比較する。

④ 左隣の値が今の値より ＿＿＿＿ とき、2つを交換する。

⑤ 交換すると、今の値は配列中を ＿＿ 方向へ1つ移動する。

⑥ 左隣の値の方が大きい間、比較と交換を繰り返す。

⑦ 値を正しい位置まで入れたら、整列済みの個数を ＿＿ 増やす。

② 右
③ 左
④ 大きい
⑤ 左
⑦ 1

4-4．必要な情報に名前を付けよう

最初は data[0] の1個だけが整列済みなので、sortedCount は1です。

sortedCount ← 1
i ← sortedCount

交換を続ける条件は、次の2つです。

まだ左端まで来ていない
かつ
左隣の値の方が大きい

4-5．疑似言語の穴を埋めよう

○insertionSort(整数型の配列: data)
    整数型: n ← dataの要素数
    整数型: sortedCount, i

    sortedCount ← ＿＿

    while (sortedCount ＜ ＿＿)
        i ← ＿＿＿＿＿＿＿＿

        while ((＿＿ ＞ ＿＿) and (＿＿＿＿＿＿＿＿ ＞ ＿＿＿＿＿＿＿＿))
            swap(＿＿＿＿＿＿＿＿, ＿＿＿＿＿＿＿＿)
            i ← ＿＿＿＿＿＿
        endwhile

        sortedCount ← sortedCount ＋ ＿＿
    endwhile

○insertionSort(整数型の配列: data)
    整数型: n ← dataの要素数
    整数型: sortedCount, i

    sortedCount ← 1

    while (sortedCount ＜ n)
        i ← sortedCount

        while ((i ＞ 0) and (data[i － 1] ＞ data[i]))
            swap(data[i － 1], data[i])
            i ← i － 1
        endwhile

        sortedCount ← sortedCount ＋ 1
    endwhile

5．3つのソートを見分けよう

練習1　説明から名前を答えよう

練習2　比較する要素を答えよう

配列が次の状態のとき、次に比較する2要素または交換候補を答えよう。

（1）バブルソート

i が2のとき：data[＿＿] と data[＿＿]

（2）選択ソート

fixedCount が2、i が5のとき、比較する値：data[＿＿] と data[＿＿＿＿]

（3）挿入ソート

i が4のとき：data[＿＿＿＿] と data[＿＿]

（1）data[2] と data[3]
（2）data[5] と data[minPos]
（3）data[3] と data[4]

練習3　1周ごとの数列からソート名を当てよう

各ソートの一番外側の処理を1周とします。次の（1）〜（3）は、1周が終わるごとの数列を、整列が完了するまで並べたものです。数列の変化を見て、バブルソート・選択ソート・挿入ソートのどれかを答えよう。

（1）

6 2 5 1 4 3
      ↓
2 5 1 4 3 6
      ↓
2 1 4 3 5 6
      ↓
1 2 3 4 5 6
      ↓
1 2 3 4 5 6
      ↓
1 2 3 4 5 6

ソート名：＿＿＿＿＿＿＿＿＿＿＿＿

（2）

6 2 5 1 4 3
      ↓
1 2 5 6 4 3
      ↓
1 2 5 6 4 3
      ↓
1 2 3 6 4 5
      ↓
1 2 3 4 6 5
      ↓
1 2 3 4 5 6

ソート名：＿＿＿＿＿＿＿＿＿＿＿＿

（3）

6 2 5 1 4 3
      ↓
2 6 5 1 4 3
      ↓
2 5 6 1 4 3
      ↓
1 2 5 6 4 3
      ↓
1 2 4 5 6 3
      ↓
1 2 3 4 5 6

ソート名：＿＿＿＿＿＿＿＿＿＿＿＿

2 5 1 4 3 [6]
2 1 4 3 [5 6]
1 2 3 [4 5 6]

[1] 2 5 6 4 3
[1 2] 5 6 4 3
[1 2 3] 6 4 5

[2 6] 5 1 4 3
[2 5 6] 1 4 3
[1 2 5 6] 4 3

6．総合問題

問題1　処理からソートを特定しよう

次の処理は、どのソートを表しているか答えよう。また、空欄を埋めよう。

while (sortedCount ＜ n)
    i ← sortedCount

    while ((i ＞ 0) and (data[i － 1] ＞ data[i]))
        swap(data[＿＿＿＿], data[＿＿])
        i ← i － 1
    endwhile

    sortedCount ← sortedCount ＋ 1
endwhile

ソート名：＿＿＿＿＿＿＿＿＿＿＿＿

swap(data[i － 1], data[i])

問題2　3つの処理を説明しよう

次の言葉を必ず使い、3つのソートの違いを日本語で説明しよう。

• 隣り合う
• 最小値
• 左隣
• 確定
• 整列済み

7．まとめ

• バブルソートは、隣り合う2つを比較して交換する
• 選択ソートは、未確定部分の最小値を探して左端と交換する
• 挿入ソートは、左隣との交換を繰り返して整列済み部分へ入れる
• 配列は0オリジンで考える
• 交換する2要素は swap(data[a], data[b]) と書く
• 1回の比較、1周、アルゴリズム全体の順に組み立てる
• トレースでは、比較対象・交換・交換後の配列を毎回書く