明らかに、出来上がるソート列の長さに比例した時間量です。以下の再帰式を満たします。問題を小分けにして、あとで組み合わせる。後半部分はピボットより大きく分割する。小分けした問題は、再帰的にソートする。クイックソートのアルゴリズムでは、ピボットの選び方にあいまいさがあります。(自由度といったほうがいいかも。)ここでは、ソート範囲の最初の要素をピボットとして説明します。実際に、プログラミングするときは、もっといろんな状況を考えましょう。8探索が交差したら終了。ピボットと前半最後の要素を交換し、あとは再帰呼び出し。8713クイックソートの実現1(分割)/*概略です。i,j;/*カウンタ*/i=left+1;j=right;for(;;){while(A[i]<A[left]){i++;}while(A[j]>A[left]){j--;}if(i>=j){break;}swap(i,j,A);}return(i);}クイックソートの実現2(再帰)/*概略です。最悪時の計算量と平均の計算量が異なります。これらは、ピボットの選び方にもよりますが、どんな選び方によっても最悪のデータ初期配置があります。ここでは、最悪計算量と、平均計算量の両方を考えます。クイックソートの最悪計算量まず、関数partition(i,j,A)の1回の時間量は、j-i+1に比例した時間量です。いつも0個、ピボット、残りのように分割されるのが最悪の場合です。ピボットとしていつも最小値が選択されたりするのが最悪です。(他にも最悪の場合はあります。)このときでも、partition(i,j,A)の実行には、j-i+1回の演算が必要です。)のアルゴリズムです。通りの並びがすべて等確率だとしましょう。以下の漸化式を満たす。大きいデータを処理する工夫2工夫:大きいデータは動かさずに、たどり方だけがわかればいい。B[1]B[i]B[n-1]添字の配列Bだけを操作して、配列Aは動かさない。(data1が最小値のとき。A[1]data1A[i]A[n-1]ソート順は、下の情報からえられる。(配列の添字の利用だけでなく、ポインタでも同様のことができる。問題の難しさ(問題固有の計算量)の上界を与えています。最適なアルゴリズムの存在範囲アルゴリズムがない問題は、難しさがわからない。問題を解くアルゴリズムが無いことを示さないといけない。実は、1つのアルゴリズムを作ることより、アルゴリズムが存在しないことを示すことの方が難しい。)?ソート問題の難しさアルゴリズムが存在しない。)ソート問題の場合は、なんとか示せます。概念的、抽象的なもの。根から葉までの道の長さが時間量に対応します。決定木にn!個以上の葉がなければならない。決定木の高さで定まる。悪いアルゴリズムは高さが高い。