Sorting · ソート
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · このページには最新のブラウザ（SharedArrayBuffer対応）が必要です。Chrome、Edge、Firefox、Safariを最新バージョンに更新してください。
English
Putting items in order
- Sorting arranges a list into order, usually smallest first.
- The key move is a swap: exchange two items.
- In Python:
a[i], a[j] = a[j], a[i]swaps two list items in one line.
日本語
順序付け
- ソートとは、リストを通常は最小値から始まるように並べ替えることです。
- 主要な操作はスワップ：2つの要素を入れ替えることです。
- Pythonでは：
a[i], a[j] = a[j], a[i]で1行目にリストの2つの要素を入れ替えられます。
English
Bubble sort
- Compare each pair of neighbours; swap them if they are out of order.
- After one full pass, the largest item has "bubbled" to the end.
- Repeat the passes until no swaps are needed.
日本語
バブルソート
- 隣り合うペアを比較し、順序が逆なら入れ替えます。
- 1回の全通過後、最大の要素が「泡」のように末尾に移動します。
- スワップが必要なくなるまで通過を繰り返します。
data = [3, 1, 2]
n = len(data)
for i in range(n - 1):
for j in range(n - 1 - i):
if data[j] > data[j + 1]:
data[j], data[j + 1] = data[j + 1], data[j]
print(data)
English
Insertion sort
- Treat the left part of the list as already sorted.
- Take the next item and slide it left until it sits in the right place.
- Like sorting playing cards in your hand, one at a time.
日本語
イントロソート（挿入ソート）
- リストの左側を既に整序済みとみなします。
- 次の要素を取り出し、正しい位置に来るまで左へスライドさせます。
- 手元のトランプを1枚ずつ並べ替えるようなものです。
data = [3, 1, 2]
for i in range(1, len(data)):
key = data[i]
j = i - 1
while j >= 0 and data[j] > key:
data[j + 1] = data[j]
j = j - 1
data[j + 1] = key
print(data)
English
Compare them
- Both check roughly
n × npairs, so both are slow on big lists. - Insertion sort is fast when the list is almost sorted already.
- Faster methods exist, but bubble and insertion are easy to understand.
日本語
比較
- どちらも約
n × nペアをチェックするため、大きなリストではどちらも遅いです。 - イントロソートはリストがほぼ整序されている場合、高速です。
- より高速な手法も存在しますが、バブルソートとイントロソートは理解しやすいです。
English
In Cambridge pseudocode
- Bubble sort with a
tempvariable for the swap.
日本語
Cambridge擬似コードにおける表現
- スワップ用の
temp変数を伴うバブルソート。
FOR i ← 0 TO LENGTH(list) - 2
FOR j ← 0 TO LENGTH(list) - 2 - i
IF list[j] > list[j + 1] THEN
temp ← list[j]
list[j] ← list[j + 1]
list[j + 1] ← temp
ENDIF
NEXT j
NEXT i
English
Common mistakes
- Bubble and insertion sort are both O(n²).
- Trace a small list by hand to check your sort works.
日本語
よくあるミス
- バブルソートとイントロソートはともにO(n²)です。
- ソートが正しく動作するか確認するために、小さなリストを手動でトレースしてください。
English
Now you try
- Each task changes the list in place — no need to return it.
- Press Check answer to test your code.
日本語
あなたも試してみよう
- 各タスクはリストをインプレイスで変更します——返す必要はありません。
- 回答を確認 を押してコードを試してください。
Explore · 探索
Watch a sort run · ソートの実行を見る
Sorting repeatedly compares and swaps until everything is in order. · ソートは反复比較・交換を行い、全てが正しい順序になるまで続ける。
Write swap(items, i, j) that exchanges the items at index i and index j in the list. Change the list in place (no return). · swap(items, i, j) を作成してください。リスト内のインデックス ⟨i⟩ と ⟨j⟩ の位置にあるアイテムを交換する関数です。リストを その場で変更 してください（戻り値はありません）。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Write bubble_sort(items) that sorts the list into ascending order using bubble sort. Change the list in place. · bubble_sort(items) を記述し、バブルソートを用いてリストを昇順にソートする。リストをin placeで変更する。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。
Write insertion_sort(items) that sorts the list into ascending order using insertion sort. Change the list in place. · insertion_sort(items) を記述し、挿入ソートを用いてリストを昇順にソートする。リストをin placeで変更する。
Click Run to see the output here. · 実行ボタンをクリックして出力を確認してください。