挿入ソート (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 についてその処理が終わった時点での配列を出力してください。