Implementation (Part 2)
Coddyの「挿入ソート - DSAシリーズ」コースのレッスン 6/9。
シナリオ: [5, 2, 9, 1, 5] のソート
ステップ 1: 初期状態
- 元の配列: [5, 2, 9, 1, 5]
- これを手札（または数値の配列）としてイメージしてください。
ステップ 2: 1番目の要素 (i=1, key=2)
- 2番目のカード（要素）から開始します: key = 2。
- 2 を 5（これまでにソート済みの唯一の要素）と比較します。
- 2 の方が小さいため、5 を右にシフトし、その場所に 2 を挿入します。
- 更新された配列: [2, 5, 9, 1, 5]
ステップ 3: 2番目の要素 (i=2, key=9)
- 次のカードに移動します: key = 9。
- 9 を 5 と比較します。
- 9 の方が大きいため、シフトする必要はありません。
- 更新された配列: [2, 5, 9, 1, 5] (変更なし)
ステップ 4: 3番目の要素 (i=3, key=1)
- 次のカードに移動します: key = 1。
- 1 を 9 と比較し、次に 5 と比較します。
- 9 と 5 を右にシフトし、1 のためのスペースを作ります。
- 更新された配列: [1, 2, 5, 9, 5]
ステップ 5: 4番目の要素 (i=4, key=5)
- 次のカードに移動します: key = 5。
- 5 を 9 と比較します。
- 5 の方が小さいため、シフトする必要はありません。
- 更新された配列: [1, 2, 5, 9, 5] (変更なし)
ステップ 6: 5番目の要素 (i=5, key=5)
- 最後のカードに移動します: key = 5。
- 5 を 9 と比較します。
- 5 の方が小さいため、シフトする必要はありません。
- 更新された配列: [1, 2, 5, 5, 9]
最終結果:
- ソート済み配列: [1, 2, 5, 5, 9]
各ステップで、カード（要素）を1枚選び、ソート済みのカードと比較して、必要に応じて他のカードをシフトしながら適切な場所に配置しています。このプロセスを配列全体がソートされるまで繰り返します。
チャレンジ
簡単次に、各要素のソートを行う内側のループを実装してください。
関数 insertionSort 内でソートを完成させてください。
この関数は、最後に配列の要素を1つずつ、間に改行を入れて出力する必要があります。
これまでのレッスンやヒントを参考にしてください :)
自分で試してみよう
def insertionSort(arr):
for i in range(1, len(arr)):
key = arr[i]
print(key)
挿入ソート - DSAシリーズのすべてのレッスン
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity