ソートとは、小さい順に並べること
ソートとは、データを小さい順や大きい順に並べる手順のことです。選択ソート、挿入ソート、マージソートの3つを、手で追います。
並べ方が違うと、手数の増え方も違います。1000個を並べるのに、約50万回の比較で済む方法と、約1万回で済む方法があります。
このレッスンのゴール
メモ
選択ソート、挿入ソート、マージソートの動きを表で追い、手数の違いを言える。
重要な言葉
| ことば | いみ |
|---|---|
| ソート | 小さい順などに並べ替えること。整列とも言う |
| 比較 | 2つの値のどちらが小さいかを調べること |
| 入れ替え | 2つの位置の値を、取り替えること |
| マージ | 並んだ2つのリストを、1つの並んだリストに合わせること |
| パス | リストを先頭から1回通ること |
学生が入力するセルは、このプレビューでは空白です。
選択ソートは最小を前に運ぶ
選択ソートは、残りの中から一番小さいものを探して、先頭に置きます。これをパスごとに繰り返します。
4個なら、比較は3回、2回、1回で合計6回です。n 個なら、n かける n-1 を2で割った回数になります。入力が最初から並んでいても、この回数は変わりません。
選択ソートの追い方
| パス | 探す範囲 | 一番小さいもの | 並びの結果 |
|---|---|---|---|
| 1 | 全部 | 10 | 10, 40, 30, 20 |
| 2 | 2番目から | 20 | 10, 20, 30, 40 |
| 3 | 3番目から | 30 | 10, 20, 30, 40 |
学生が入力するセルは、このプレビューでは空白です。
選択ソートをパスごとに見る
# 選択ソート: 残りの中で一番小さいものを、先頭に持ってきます。
prices = [400, 100, 300, 200]
for start in range(len(prices) - 1):
smallest = start
for i in range(start + 1, len(prices)):
if prices[i] < prices[smallest]:
smallest = i
# 一番小さいものと、先頭の位置のものを入れ替えます。
keep = prices[start]
prices[start] = prices[smallest]
prices[smallest] = keep
print("パス", start + 1, prices)
# prices に 50 を足して、パスの数を見ましょう。
挿入ソートは手札のように入れる
挿入ソートは、トランプの手札を並べるのと同じです。1枚ずつ取り、すでに並んだ部分の正しい場所に入れます。
最初から並んでいれば、各回の比較は1回です。全部で n-1 回しかかかりません。逆順のときは、選択ソートと同じ程度まで増えます。
挿入ソートの追い方
| 取る値 | 並んだ部分 | 入れたあと |
|---|---|---|
| 30 | 空 | 30 |
| 10 | 30 | 10, 30 |
| 40 | 10, 30 | 10, 30, 40 |
| 20 | 10, 30, 40 | 10, 20, 30, 40 |
学生が入力するセルは、このプレビューでは空白です。
マージソートは半分に分けて合わせる
マージソートは、リストを半分に分け続けて、1個ずつにします。そのあと、並んだ2つをマージして戻していきます。
分ける段は、n を2で割り続ける回数です。各段で n 個を動かすので、全体は n かける段の数です。1024個なら、10段で約1万回です。
2つの並んだリストを合わせる
| 左の先頭 | 右の先頭 | 取る値 | 合わせた結果 |
|---|---|---|---|
| 3 | 1 | 1 | 1 |
| 3 | 6 | 3 | 1, 3 |
| 8 | 6 | 6 | 1, 3, 6 |
| 8 | 右が空 | 8 | 1, 3, 6, 8 |
学生が入力するセルは、このプレビューでは空白です。
手数の違い: 比較の回数
| n | 選択ソート n(n-1)/2 | マージソート n かける段 |
|---|---|---|
| 8 | 28 | 24 |
| 64 | 2016 | 384 |
| 1024 | 523776 | 10240 |
学生が入力するセルは、このプレビューでは空白です。
よくある間違い
注意
マージソートが、いつも一番いいと思いがちです。マージソートは、合わせるための別のリストが要ります。数が少ないときや、ほぼ並んでいるときは、挿入ソートの方が簡単で、手数も少なくて済みます。
ラボの端末でソートとマージを使う
下の Run で、本物のソートを使います。sort -n は数として小さい順に並べ、sort -m は、並んだ2つのファイルをマージします。
先にラボの /tmp に、並んだ2つの小さなファイルを作ります。マージの結果を、自分で予想してから Run しましょう。
数を小さい順に並べる
printf '%s\n' 5 2 9 1 | sort -n | paste -sd' 'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
左のファイルを作る
printf '1\n4\n9\n' > /tmp/alg-a.txtここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
右のファイルを作る
printf '2\n7\n10\n' > /tmp/alg-b.txtここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
2つをマージする
sort -m -n /tmp/alg-a.txt /tmp/alg-b.txt | paste -sd' 'ここでは表示のみで、実行されません。無料アカウントを作成すると、実行ボタンで自分のラボのターミナルに入力できます。
さらに挑戦: 逆順のとき
課題が通ったら、[4, 3, 2, 1] を挿入ソートで並べる比較の回数を、表で数えましょう。
次に、[1, 2, 3, 4] の場合と比べます。最初の並びで手数が変わる理由を、自分の言葉で説明しましょう。