バブルソート

挿入ソートと違い、あらかじめ床に並べてあるトランプを整列させる。
(結局全部並べた暁には、メモリの使用量は同じだけれど・・・。)

考え方は簡単で、一番後ろの要素から一つずつ比較していく。
全要素比較したあとでは、要素がソートされている。
ここではフラグを使ってもう交換ができない(ソート済み)ときにループを抜けるが、
if文で判定してもOK。(というか、そっちの方が一般的だと思う・・・。)

バブルソートの特徴は安定なソートであること。
安定なソートとは、ソートのキーが同じ場合、なんどやっても同じ順番になるということ。
ただし、隣同士を比較する演算「A[j] < A[j - 1]」を「A[j] <= A[j - 1]」とすると、キーが同じ場合に
比較演算をしてしまうため、安定でなくなるので注意。

計算量は、最悪の場合はすべて逆順のときで、挿入ソートと同じくデータ数Nの時
(N-1) + (N-2) + …+ 2 + 1 = N(N-1)/2
となる。

■ソースコードgithub.com

■参考資料

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造