挿入ソート

挿入ソート（Insertion Sort）は、手持ちのトランプを並び替えるときに使われる、自然で思い付きやすいアルゴリズムの１つです。片手に持ったトランプを左から小さい順に並べる場合、１枚ずつカードを取り出して、それをその時点ですでにソートされている並びの適切な位置に挿入していくことによって、カードを並べ替えることができます。

挿入ソートは次のようなアルゴリズムになります。

# 要素数Nの配列の要素を挿入ソートで昇順に整列する
def insertion_sort(N, A):
    for i in range(1, N):            # 0オリジンで1から開始する
        key = A[i]                   # 挿入する要素keyを保持する
        j = i - 1                    # 現在置の１つ前から
        while j >= 0 and A[j] > key: # keyを挿入する位置を探す
            A[j + 1] = A[j]          # keyより大きい要素を後方に１つ移動する
            j -= 1
        A[j + 1] = key               # 空いた位置にkeyを挿入する

N 個の要素を含む数列 A を昇順に並び替える挿入ソートのプログラムを作成してください。上の疑似コードに従いアルゴリズムを実装してください。アルゴリズムの動作を確認するため、各計算ステップでの配列（入力直後の並びと、各 i の処理が終了した直後の並び）を出力してください。

入力

入力の最初の行に、数列の長さを表す整数 N が与えられます。2 行目に、N 個の整数が空白区切りで与えられます。

出力

出力は N 行からなります。挿入ソートの各計算ステップでの途中結果を 1 行に出力してください。配列の要素は１つの空白で区切って出力してください。最後の要素の後の空白など、余計な空白や改行を含めると Presentation Error となりますので注意してください。

制約

• 1 ≤ N ≤ 100
• 0 ≤ A の要素 ≤ 1,000

入力例 1

6
5 2 4 6 1 3

入力例 1 に対する出力

5 2 4 6 1 3
2 5 4 6 1 3
2 4 5 6 1 3
2 4 5 6 1 3
1 2 4 5 6 3
1 2 3 4 5 6

入力例 2

3
1 2 3

入力例 2 に対する出力

1 2 3
1 2 3
1 2 3

Note

Algorithm

 

---