【メモ】

平均の場合、任意の順序統計(特に中位数)は、線形時間内に得ることができる.

int partition(int A[],int p,int r) {
    int x = A[r];
    int i = p-1;
    for (int j=p;j<r;j++) {
        if (A[j] <= x) {
            i++;
            swap(A[i],A[j]);
        }
    }
    swap(A[i+1],A[r]);
    return i+1;
}
int randomizedPartition(int A[],int p,int r) {
    int i = rand() % (r-p+1) + p;
    swap(A[r],A[i]);
    return partition(A,p,r);
}
int randomizedSelect(int A[],int p,int r,int i) {
    if (p==r) return A[p];
    int q = randomizedPartition(A,p,r);
    int k = q-p+1;
    if (i==k) return A[q];
    else if (i<k) return randomizedSelect(A,p,q-1,i);
    else return randomizedSelect(A,q+1,r,i-k);
}

【課題】

9.2-1証明:RANDOMizeD-SELECTでは、長さが0の配列に対して、再帰的に呼び出されない.
シナリオ1:r=pの場合、直接A[p]に戻り、長さが0の配列は現れない.
シナリオ2:r−p=1の場合、q=pまたはr.q=pの場合、答えはA[q]にあるか、A[r]にあるか、i=kの場合、A[q]に戻るか、そうでなければ区間(q+1,r)を再帰し、シナリオ1が現れる.q=rの場合は同じです.
シナリオ3:r>p+1の場合、qが境界、すなわちq=rまたはq=pの場合、答えがA[q]の場合、シナリオ1に移る.そうでなければ、シナリオ3またはシナリオ2に移動します.
したがって,再帰中に長さ0の配列は現れない.
9.2−2は、インジケータランダム変数XkおよびT(max(k−1,n−k))が独立であることを証明する.
9.2-3 RANDOMizeD-SELECTの反復バージョンを書き出します.

int NonRecursiveRandomizedSelect(int A[],int p,int r,int i) {
    while (p<r) {
        int q = randomizedPartition(A,p,r);
        int k = q-p+1;
        if (i==k) return A[q];
        else if (i<k) r = q-1;
        else {
            p = q+1;
            i -= k;
        }
    }
    return A[p];
}

9.2-4配列A=<3,2,9,0,7,5,4,8,6,1>の最小要素をRANDOMizeD-SELECTで選択すると仮定する.RANDOMizeD−SELECTの最悪の場合の性能における分割シーケンスを与える.
9、8、7、6、5、4、3、2、1、0 orz