Insertion sort (挿入ソート)
Insertion sort（挿入ソート）は、selection sort（選択ソート）アルゴリズムによく似ています。非常に直感的で、配列の左側を常にソート済みの状態に保ちながら、右の要素へと進んでいく方法を取ります。
より具体的には、insertion sort（挿入ソート）では、左端の要素から始めて、右方向へ徐々に移動していきます。そして、もし現在見ている要素が左側にある要素よりも小さい場合は、それが正しい位置に収まるように、左側の要素を一つずつ右にずらして空いた場所に現在の値を挿入します。例えば、
[0, 2, 4, 1, 10, 8] という配列で現在の要素が 1 のときは、まず 4 を右に移動し、続いて 2 を右に移動した後、0 と 2 の間に 1 を置きます。すると、[0, 1, 2, 4, 10, 8] になります。次に 10 を見ますが、左側よりも大きいため何もしません。最後に 8 を見て、10 を右にずらすことで 8 を 4 と 10 の間に挿入します。a = [...]
for i in range(1, len(a)): # 2番目の要素から開始
while i > 0 and a[i] < a[i - 1]: # 現在の要素がひとつ前より小さい間は
a[i - 1], a[i] = a[i], a[i - 1] # 現在の要素とその前の要素を入れ替える
i -= 1 # 現在の要素のインデックスを追跡する
print(a)insertion sort（挿入ソート）は、注目している要素をソート済みの領域に正しく挿入していくアルゴリズムです。最悪の場合（例えば、配列が降順に並んでいるとき）は、現在の要素より前にあるすべての要素を右にずらす必要があるため、全体で の操作が必要になります。
アルゴリズムをいくつかの配列でシミュレーションしてみましょう。
[4, 1, -1, 0, 2, 8]
i = 1⇒ swap ⇒[1, 4, -1, 0, 2, 8]
i = 2⇒ swap ⇒[1, -1, 4, 0, 2, 8]⇒ swap ⇒[-1, 1, 4, 0, 2, 8]
i = 3⇒ do nothing
i = 4⇒ swap ⇒[-1, 1, 0, 4, 2, 8]⇒ swap ⇒[-1, 0, 1, 2, 4, 8]
i = 5⇒ do nothing
- print
[-1, 0, 1, 2, 4, 8]
[10, 5, 1, -7]
i = 1⇒ swap ⇒[5, 10, 1, -7]
i = 2⇒ swap ⇒[5, 1, 10, -7]⇒ swap ⇒[1, 5, 10, -7]
i = 3⇒ swap ⇒[1, 5, -7, 10]⇒ swap ⇒[1, -7, 5, 10]⇒ swap ⇒[-7, 1, 5, 10]
[1, 2, 3, 4, 5]
i = 1⇒ do nothing
i = 2⇒ do nothing
i = 3⇒ do nothing
i = 4⇒ do nothing
Challenge
与えられた
n 個の整数を、insertion sort（挿入ソート）を使って昇順に並べ替えてください。入力
最初の行には、配列の要素数を示す整数
n (1 ≤ n ≤ 1000) が与えられます。次の行には、
n 個の整数 ( ≤ ≤ ) が空白区切りで与えられます。出力
入力として与えられた配列を昇順にソートした結果を出力してください。
Examples
Input | Output |
5
5 5 3 2 3 | 2 3 3 5 5 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB