読者です 読者をやめる 読者になる 読者になる

ALDS1_2 Bubble sortを解く話

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

 

特徴

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

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

 

アルゴリズム

  1. Bubblesort(A)
  2.     n = A.length
  3.     for i = 0 to n - 1
  4.         for j = n - 1 downto 1
  5.             if(A[j] < A[j - 1])
  6.                 swap(A[j], A[j - 1])

 

実装

gist14532d31250bad311cb0fd295619e621

 

計算量

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

 

感想

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

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

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