クイックソートの最悪時の計算量がO(n^2)であることの証明

ソートする対象の数の配列を2,4,9,10,6,3,1とする。

基準値を中央値である10とする。

そうした場合、10より小さい値は10より左、大きい値は右に配置する。

そこで、2から順に見ていくと10が1番大きいことが分かるので、配列は、

2,4,9,6,3,1,10

となる。この際、全ての値を1つずつ見ていくことになるので、10以外の値をみる。つまり、配列の要素数をnとすると、計算量はn-1となる。

次に10を残した残りの配列、2,4,9,6,3,1を考える。ここでは基準値を9とすると、10と9以外の値を1つずつ確認していくことになるので、計算量はn-2となる。そして、この時の配列は

2,4,6,3,1,9,10

となる。

次に2,4,6,3,1をみていく。ここでの基準値は6とすると、先ほどの10,9の時と同様、10,9,6以外の値を1つずつ確認していくことになるので、計算量はn-3となる。そして、この時の配列は

2,4,3,1,6,9,10

となる。

次に2,4,3,1をみていく。ここでの基準値は4とすると、先ほどの10,9,6の時と同様、10,9,6,4以外の値を1つずつ確認していくことになるので、計算量はn-4となる。そして、この時の配列は

2,3,1,4,6,9,10

となる。

次に2,3,1をみていく。ここでの基準値は3とすると、先ほどの10,9,6,4の時と同様、10,9,6,4,3以外の値を1つずつ確認していくことになるので、計算量は2となる。そして、この時の配列は

2,1,3,4,6,9,10

となる。

最後に2,1をみていく。ここでの基準値は2とすると、先ほどの10,9,6,4,3の時と同様、10,9,6,4,3,2以外の値を確認していくことになるので、計算量は1となる。そして、この時の配列は

1,2,3,4,6,9,10

となり、ソートが完了した。

以上のことから、オーダーは

n-1 + n-2 + … +1

= {n × (n-1)}/2

→O(n^2)

と、求められる。