クイックソート：パーティショニングの分析

Question

私はアルゴリズム4、ロバートセジウィックのコースでクイックソートを勉強しています。

Iはクイックソートのコードの次のパーティションは、私は上記のコードのT（n）を知りたい長N

private static int partition(Comparable[] a, int lo, int hi) 
{ 
    int i = lo, j = hi+1; 
    while (true) 
    { 
    while (less(a[++i], a[lo])) 
     if (i == hi) break; 

    while (less(a[lo], a[--j])) 
     if (j == lo) break; 

    if (i>= j) break; 
    exch(a, i, j); 
    } 

    exch(a, lo, j); 
    return j; 
} 

の配列に比較の数を知っているたいです。 （比較）

私の考えでは、2Nの比較が必要です。

iが左から右へ移動するのにNが必要であり、jが既に配列（A、B、C、D、E、 F、G、H）。

が（=より少ないと比較）

Answer 1

このパーティション関数の時間複雑さは私の神、それはiの繰り返しで私のミスだT(n) = O(n)

Answer 2

です。唯一の1が比較取る停止するiを発見する過程では、

。

だから、〜Nの比較が必要です。