反転数を考慮したクイックソートの計算量解析

摘要

In this work, we look at relationship of the quick sort algorithm with input characteristics. The complexity of the quick sort is Θ(n log n) on average, but Θ(n~2) in worst case. In particular, the worst-case is achieved when the input is already sorted. Therefore, we may consider that the complexity of the quick sort is large when the input is sorted to some extent, and small otherwise. To study the complexity in terms of "sortedness" we use the number of inversions of the input permutation as an input characteristic, and try to analyze the complexity with the number of inversions. We obtain some theoretical results on the worst-case, the average-case and the best-case complexity.%本研究では，クイックソートの入力の特性と計算量の関連性に着目した．クイックソートは期待計算量がΘ（n log n）であるが，入力によっては最悪でΘ（n~2）の計算量を必要とする．特に，ソート済みの順列を入力した場合に計算量が多くなると言われていることから，「クイックソートの計算量はある程度整列している入力に対して大きいが，そうでない場合に小さくなるのではないか」と考えられる．この考察を理論的に推し進めるため，入力順列の「整列度合い」の指標として順列の反転数を用いて，計算量の解析を試みた．そして，最悪計算量，期待計算量，最良計算量に関して理論的な結果を得た．