３つの基本的なソートアルゴリズム
3つのソートを手でやってみよう
今日やること
これから、同じ6個の数字を使って、
- バブルソート
- 選択ソート
- 挿入ソート
の3種類の並べ替えを、プログラムを書かずに自分の手で実行します。
最初の数字は、すべて同じです。
6 2 5 1 4 3
目標は、小さい順に
1 2 3 4 5 6
と並べることです。
この課題では、まだプログラムの変数や繰り返し処理は使いません。
まずは、
「数字を並べ替えるとき、実際にどんな作業を繰り返しているのか」
を自分の手で確かめてみましょう。
1．バブルソートを手でやってみよう
1-1．バブルソートのルール
バブルソートでは、隣り合った2つの数字を比較します。
左の数字の方が大きければ、その2つを交換します。
そして、比較する場所を1つ右へ動かします。
これを左から右まで繰り返します。
1-2．まず、やり方を見てみよう
次の数字を使って、1周だけやってみます。
4 1 3 2
最初の2つを比較します。
[4 1] 3 2 swap(4, 1)
1 4 3 2
次の隣り合った2つを比較します。
1 [4 3] 2 swap(4, 3)
1 3 4 2
さらに次へ進みます。
1 3 [4 2] swap(4, 2)
1 3 2 4
これで1周終了です。
一番大きい 4 が、一番右まで移動しました。
1-3．同じようにやってみよう
では、次の6個の数字を同じ方法で並べ替えます。
開始：
6 2 5 1 4 3
1周目
左から順番に、隣り合った2つを比較していきます。
必要なら交換し、交換したときは swap(○, ○) も書きましょう。
開始
6 2 5 1 4 3
↓
________________________________________
↓
________________________________________
↓
________________________________________
↓
________________________________________
↓
________________________________________
1周目が終わった状態：
________________________
一番右に来た数字は何ですか？
________
その数字は、もう動かす必要がありそうですか？
ある ・ ない
1-4．2周目
1周目で位置が決まった一番右の数字は、もう比較しません。
同じように、残った部分を左から右へ調べます。
開始
________________________
↓
________________________________________
↓
________________________________________
↓
________________________________________
↓
________________________________________
2周目が終わった状態：
________________________
1-5．3周目
開始
________________________
↓
________________________________________
↓
________________________________________
↓
________________________________________
3周目が終わった状態：
________________________
1-6．4周目
開始
________________________
↓
________________________________________
↓
________________________________________
4周目が終わった状態：
________________________
1-7．5周目
開始
________________________
↓
________________________________________
5周目が終わった状態：
________________________
1-8．バブルソートをやって気付いたこと
バブルソートでは、どんな2つの数字を比べていましたか？
________________________________________
1周するたびに、どちら側から数字の位置が決まっていきましたか？
左側 ・ 右側
1周目と2周目では、比較する回数は同じでしたか？
同じ ・ 違う
なぜそうなったと思いますか？
________________________________________
________________________________________
2．選択ソートを手でやってみよう
最初の状態に戻します。
6 2 5 1 4 3
2-1．選択ソートのルール
選択ソートでは、
まだ並べ終わっていない部分から、一番小さい数字を探す
という作業をします。
一番小さい数字を見つけたら、まだ並べ終わっていない部分の一番左の数字と交換します。
2-2．まず、やり方を見てみよう
次の数字でやってみます。
4 2 3 1
まだ全部が未確定なので、まず全体から一番小さい数字を探します。
一番小さい数字は 1 です。
未確定部分の一番左にある 4 と交換します。
[4] 2 3 [1] swap(4, 1)
1 2 3 4
これで、一番左の 1 の位置が決まりました。
1 | 2 3 4
次は、残った
2 3 4
の中から一番小さい数字を探します。
一番小さい数字はすでに左端の 2 なので、交換する必要はありません。
1 | 2 3 4 交換なし
このように、
一番小さい数字を探す → 未確定部分の左端と交換する
を繰り返します。
2-3．同じようにやってみよう
次の6個の数字を、同じ方法で最後まで並べ替えましょう。
開始：
6 2 5 1 4 3
1回目
未確定部分から一番小さい数字を探し、左端と交換します。
________________________________________
________________________________________
1回目が終わった状態：
________________________
2回目
すでに確定した左側は調べません。
________________________________________
________________________________________
2回目が終わった状態：
________________________
3回目
________________________________________
________________________________________
3回目が終わった状態：
________________________
4回目
________________________________________
________________________________________
4回目が終わった状態：
________________________
5回目
________________________________________
________________________________________
5回目が終わった状態：
________________________
2-4．選択ソートをやって気付いたこと
1回の処理で、まず何を探していましたか？
________________________________________
見つけた数字は、どの数字と交換していましたか？
________________________________________
どちら側から数字の位置が決まっていきましたか？
左側 ・ 右側
3．挿入ソートを手でやってみよう
もう一度、最初の状態に戻します。
6 2 5 1 4 3
3-1．挿入ソートのルール
挿入ソートでは、左側を
すでに小さい順に並んでいる部分
として考えます。
最初は数字が1個だけなので、
6 | 2 5 1 4 3
左側の 6 だけなら、すでに並んでいます。
次に、その右隣の数字を左側の並んでいる部分へ入れていきます。
左隣の数字と比べて、左隣の方が大きければ交換します。
そして、さらに左隣と比べます。
正しい位置に来るまで、この交換を繰り返します。
3-2．まず、やり方を見てみよう
次の数字でやってみます。
4 | 3 1 2
まず 3 を左側の並んでいる部分へ入れます。
左隣の 4 の方が大きいので交換します。
[4 3] 1 2 swap(4, 3)
3 4 | 1 2
次は 1 を入れます。
まず左隣の 4 と交換します。
3 [4 1] 2 swap(4, 1)
3 1 4 2
まだ左隣の 3 の方が大きいので、もう一度交換します。
[3 1] 4 2 swap(3, 1)
1 3 4 | 2
このように、
左隣と比べる → 左隣の方が大きければ交換する
を繰り返すことで、数字を正しい位置へ入れていきます。
3-3．同じようにやってみよう
次の6個の数字を、同じ方法で最後まで並べ替えましょう。
開始：
6 | 2 5 1 4 3
1回目
________________________________________
________________________________________
1回目が終わった状態：
________________________
2回目
________________________________________
________________________________________
2回目が終わった状態：
________________________
3回目
必要なだけ左隣との交換を繰り返します。
________________________________________
________________________________________
________________________________________
________________________________________
3回目が終わった状態：
________________________
4回目
________________________________________
________________________________________
________________________________________
4回目が終わった状態：
________________________
5回目
________________________________________
________________________________________
________________________________________
________________________________________
5回目が終わった状態：
________________________
3-4．挿入ソートをやって気付いたこと
毎回、どちら側が小さい順に並んだ状態になっていましたか？
左側 ・ 右側
新しく入れる数字は、何と比較していましたか？
________________________________________
左隣の数字の方が大きいとき、何をしていましたか？
________________________________________
どこまで交換を繰り返していましたか？
________________________________________
4．3つのソートを比べてみよう
ここまで自分でやった結果を使って整理しましょう。
| ソート | 何を繰り返していた？ | どちら側から整っていく？ |
|---|---|---|
| バブルソート | ______________________________ | ______ |
| 選択ソート | ______________________________ | ______ |
| 挿入ソート | ______________________________ | ______ |
5．自分の言葉でまとめよう
バブルソート
どんな並べ替え方でしたか？
________________________________________
________________________________________
選択ソート
どんな並べ替え方でしたか？
________________________________________
________________________________________
挿入ソート
どんな並べ替え方でしたか？
________________________________________
________________________________________
6．次に考えること
ここまでの課題では、数字を並べ替えるために、
- 同じような比較
- 同じような交換
- 同じような探索
- 同じような移動
を何度も繰り返しました。
次は、
この「何度も繰り返した作業」を、疑似言語ではどう書けばよいか
を考えていきます。