成績表を点数順に並べる
テストの結果が、出席番号の順で並んでいます。先生はそれを、点数の高い順に並べ替えたいと思っています。
並べ替えの手順には、考え方の違う種類がいくつかあります。どれも最後は同じ並びになりますが、途中でする仕事が違います。
このレッスンのゴール
メモ
バブルソート、挿入ソート、マージソートで、リストを並べ替えられる。
重要な言葉
| ことば | いみ |
|---|---|
| ソート | 値を小さい順や大きい順に並べ替えること |
| 交換 | 隣り合う二つの値の位置を入れ替えること |
| パス | リストを端から端まで一回通ること |
| マージ | 整列済みの二つのリストを、一つの整列済みにまとめること |
| 安定 | 同じ値の順番を、並べ替えのあとも保つこと |
学生が入力するセルは、このプレビューでは空白です。
バブルソートは隣どうしを比べる
バブルソートは、隣り合う二つを比べ、左が大きければ入れ替えます。これを端まで一回やるのが、一つのパスです。
一回のパスで、一番大きな値が右の端に落ち着きます。パスを重ねると、右から順に決まります。
例：5, 2, 4, 1 のバブルソート
| パス | パスの前 | パスの後 | 交換の回数 |
|---|---|---|---|
| 1 | 5, 2, 4, 1 | 2, 4, 1, 5 | 3 |
| 2 | 2, 4, 1, 5 | 2, 1, 4, 5 | 1 |
| 3 | 2, 1, 4, 5 | 1, 2, 4, 5 | 1 |
学生が入力するセルは、このプレビューでは空白です。
バブルソートの交換を数える
docker exec jupyter python3 -c 'exec("items = [5, 2, 4, 1]\nswaps = 0\nfor turn in range(3):\n for at in range(3 - turn):\n if items[at] > items[at + 1]:\n keep = items[at]\n items[at] = items[at + 1]\n items[at + 1] = keep\n swaps = swaps + 1\nprint(items, swaps)")'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
挿入ソートは手札を並べる
トランプを手札に並べるとき、新しい一枚を、すでに並んだ札の正しい場所に差し込みますよね。挿入ソートはそれと同じです。
リストの左側を整列済みの手札と考えます。次の値を取り、手札の中の正しい位置まで、大きい値を右へずらして差し込みます。
例：5, 2, 4, 1 の挿入ソート
| 取る値 | 手札の前 | 手札の後 |
|---|---|---|
| 2 | 5 | 2, 5 |
| 4 | 2, 5 | 2, 4, 5 |
| 1 | 2, 4, 5 | 1, 2, 4, 5 |
学生が入力するセルは、このプレビューでは空白です。
挿入ソートでずらした回数を数える
docker exec jupyter python3 -c 'exec("items = [5, 2, 4, 1]\nmoves = 0\nfor at in range(1, 4):\n value = items[at]\n back = at - 1\n while back >= 0 and items[back] > value:\n items[back + 1] = items[back]\n back = back - 1\n moves = moves + 1\n items[back + 1] = value\nprint(items, moves)")'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
マージソートは分けて、合わせる
マージソートは、リストを一つずつの値になるまで分けます。一つだけのリストは、すでに整列済みです。
あとは、整列済みの二つを先頭どうしで比べ、小さいほうから取り出して合わせます。これを一つのリストになるまで続けます。
例：2, 5 と 1, 4 をマージ
| 比べる先頭 | 取り出す値 | 合わせたリスト |
|---|---|---|
| 2 と 1 | 1 | 1 |
| 2 と 4 | 2 | 1, 2 |
| 5 と 4 | 4 | 1, 2, 4 |
| 5 だけ残る | 5 | 1, 2, 4, 5 |
学生が入力するセルは、このプレビューでは空白です。
二つの整列済みを合わせる
docker exec jupyter python3 -c 'exec("left = [2, 5]\nright = [1, 4]\nmerged = []\nwhile len(left) > 0 and len(right) > 0:\n if left[0] <= right[0]:\n merged.append(left.pop(0))\n else:\n merged.append(right.pop(0))\nprint(merged + left + right)")'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
よくある間違い
注意
マージするときに、二つのリストを全部つなげてから並べ替えればよいと考えがちです。それでは、整列済みという利点を捨てています。先頭どうしを比べて、小さいほうから取り出せば、一回通るだけで済みます。
どのソートを選ぶか
バブルソートと挿入ソートは、短いリストなら手順が単純で書きやすいです。リストが長くなると、仕事の量が急に増えます。
マージソートは、分けて合わせるので、長いリストでも仕事の量の増え方がゆるやかです。この違いは、次のレッスンで数えて確かめます。