素朴なソートアルゴリズムメニューのサムネイル
挿入ソート (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

順序付け可能なデータの列を、昇順または降順に並び替える操作をソートと呼びます。「データ」は、数値や文字列、オブジェクトなどあらゆるものを指します。

ソート処理はいたるところで利用されています。


・得点表を元にしてランキングを作成する

    一番素朴なソートの使い方です。


・データの集まりから、上位k個を取ってくる

    ソートをしてから先頭のk個を取ればよいです。


・貪欲アルゴリズムの前処理

    データを大きい (小さい) 順に貪欲に処理を行っていくようなアルゴリズムの前処理として、ソートは有効です。


---


挿入ソートは、データ列を「整列済み」と「未整列」の2つに分け、「未整列な配列」からデータを1つ取り出し、「整列済み配列」の適切な位置に挿入することを繰り返す手法です。「未整列な配列」が空になるまで処理を繰り返すと、1つの「整列済み配列」が得られます。この手法は、手持ちのトランプを並び替える際などによく用いられる、自然で比較的直感的なものです。


挿入ソート (昇順) は以下のようなアルゴリズムです。初期状態では A[0] ~ A[0] を「整列済み」、A[1] ~ A[n-1] を「未整列」とします。


insertion_sort(A : 配列, n : Aの要素数)
for i = 1 to n-1
// A[i] を、整列済みの A[0] ~ A[i-1] の適切な位置に挿入する

// 実装の都合上、A[i] の値が上書きされてしまうことがあるので、予め A[i] の値をコピーしておく
x <- A[i]

// A[i] の適切な挿入位置を表す変数 j を用意
j <- i-1

// A[i] の適切な挿入位置が見つかるまで、A[i] より大きい要素を1つずつ後ろにずらしていく
while j >= 0 AND A[j] > x
A[j+1] = A[j]
j--

// A[i] を挿入
A[j+1] <- x

// A[0] ~ A[i] が整列済みになった




挿入ソートの計算量を考えます。最も多くの計算ステップがかかるのは、while ループ中で値をずらす処理です。よって、この処理が最大で何回行われるかに注目し、計算量を導きます。各 i について、while ループ中で値をずらす処理は最大で i 回行われます。つまり、最悪の場合この処理は全体で 1 + 2 + ... + n-1 = (n-1)*n/2 = (n^2-n)/2 回行われます。よって、挿入ソートは O(n^2) のアルゴリズムとなります。


挿入ソートは、入力される配列によって効率が変わるアルゴリズムです。例えば、入力される配列が予め昇順にソートされている場合は値をずらす処理が全く行われませんが、降順にソートされている場合は (n^2-n)/2 回行われます。


---


では、要素数 n の数列を昇順にソートする挿入ソートのプログラムを作成してください。上の疑似コードに従って実装してください。アルゴリズムが正しく実装されていることを確認するために、各 i についてその処理が終わった時点での配列を出力してください。

入力される値

n
A_1 A_2 ... A_n

・ 入力はすべて整数
・ 1行目に、配列の要素数 n が与えられます。
・ 2行目に、配列の要素 A_1, A_2, ... , A_n が半角スペース区切りで与えられます。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

n-1 行出力してください。
i 行目 (1 ≦ i ≦ n-1) には、i 回目のループ処理が終わった時点 (つまり、A_i を整列済み配列に挿入した直後の配列) の配列を出力してください。配列の各要素を半角スペースで区切り、配列の先頭や末尾に余計な空白を入れないようにしてください。
また、末尾に改行を入れ、余計な文字、空行を含んではいけません。

A_1 A_2 ... A_n
A_1 A_2 ... A_n
...
A_1 A_2 ... A_n

条件

すべてのテストケースにおいて、以下の条件をみたします。

・ 5 ≦ n ≦ 1,000
・-10,000 ≦ A_i ≦ 10,000

入力例1

5
4 1 3 5 2

出力例1

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

問題一覧へ戻る

ページの先頭へ戻る