次はC言語で書かれたクイックソートを行う関数である
aを配列,L,Rを配列の添字とすると,関数呼出しquicksort(a,L,R)はa[L],a[L+1],…a[R]をソートする

quicksort(int a[],int left,int right)
{
int p,i,pivot,temp;
if(left<right){
pivot=a[left];
p=left;
for(i=left+1;i<=right;++i){
/*(A)*/if(a[i]<pivot){
++p;
temp=a[p];a[p]=a[i];a[i]=temp;
}
}
a[left]=a[p];
a[p]=pivot;
quicksort(a,left,p-1);
quicksort(a,p+1,right);
}
}

(1)関数呼び出しquicksort(a,L,R)はa[L],a[L+1],…,a[R]をソートし計算が停止する.このことを説明せよ
(2)整数n≧1に対して,quicksort(a,0,n-1)を呼び出してからこの計算が終了するまでのコメント(A)の置かれた行のa[i]<pivotの不等号の比較回数を
再帰呼出しされた呼出しの実行の分まで合わせて,数えることを考える
a[0],a[1],…,a[n-1]がそれぞれ互いに異なる1からnまでの整数値をとり,そのとり方は等確率であるとき
比較回数の平均値をf(n)とすると,f(n)<2(n+1)log(n+1)-2nであることを示せ