計算量の解析

各種ソート法の計算量については, たとえばセジビックのアルゴリズムの本が詳しい [1]. 結論だけのべておくと, $n$ 個のデータをバブルソートするための計算量は $O(n^2)$, クイックソートするための平均計算量は $O(n \log n)$ である.