バブルソート (paizaランク B 相当)

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

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


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

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


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

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


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

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


---


バブルソートは、データ列の隣り合う要素を比較し交換することを繰り返すことによりデータ列をソートする手法です。バブルとは「泡」の意味で、ソートの過程でデータが移動する様子が、水中で泡が浮かんでいくように見えることからこの名前がついています。


バブルソート (昇順) は以下のようなアルゴリズムです。

bubble_sort(A : 配列, n : Aの要素数)
    for i = 0 to n-2
        for j = n-1 down to i+1
            if a[j-1] > a[j] then
                swap(a[j-1], a[j])

データ列を左から右へ昇順ソートすることを考えます。バブルソートの基本方針は、左の要素と比較し、左の方が大きければ交換するです。これを右から左まで1回行うと、最小の要素が一番左に移動します。 (首を左に傾けてこの処理を眺めると、泡が水面へと上がっていく様子に見えてきませんか？) 次に、一番左の要素を除いて、同じ処理を繰り返します。すると、2番目に小さい要素が左から2番目に移動します。これを最後まで繰り返せば、ソート完了です。


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


---


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