ALDS1_2 Bubble sortを解く話 - tooshitaka’s diary

そらで書けないと恥ずかしいバブルソートを実装する．

・「泡がぶくぶく．．．」という説明で有名

・配列の要素数が大きい場合は計算量が大きくなるので非実用的

最悪ケースでは外側のループが回るたびに， $n - 1$ 回， $n - 2$ 回，...., $１$ 回の比較をする．
これらを全部足すと $n ( n - 1 ) / 2$ 回．なので計算量は $O(n^2)$ ．

バブルソートの問題は前に解いたのだが，今回ここに書くために改めて実装した．

ただ前回と違い，問題に記載してる疑似コードを見ないですぐに書けるようになっていた（内側のループをインクリメントで書くミスをしたが）．

「バブルソートなんぞ簡単な問題で」と言われてしまうかもしれないが，前回はAOJ本をほぼ写経するレベルだったので，自分の成長を確認できてうれしい．