左または右端の要素がピボットとして選択されていると、クイックソートがO（n^2）を取るようになります。

Question

クイックソートを学習しようとしています。しかし、ピボットとして左端または右端の要素を取るとき、O（n^2）ではなくO（n^2）で実行されるようです...

私のコードで何が問題なのかわかりませんが、ほとんどの場合、いくつかの非常に基本的なばかげたミスを犯します。誰でも助けてくれてどこに間違っているのか説明してくれますか？

ありがとうございます！ここに私のコードは次のとおりです。出力の

#include <iostream> 
    #include <vector> 

    typedef int64_t int64; 

    int64 numberOfComparisons; 

    using namespace std; 
    int partitionAroundPivot(vector<int64>& a, int l, int r) { 

    numberOfComparisons = numberOfComparisons + (r - l) - 1 ; 


    int ppos; 
    ppos = l; 


    int64 p = a[ppos]; //Gives pivot 

    if(ppos != l) 
     swap(a[ppos], a[l]); 

    int i = l + 1, j; 
    for(j = l + 1; j <= r; j++){ 
     if(a[j] < p) 
     { 
      swap(a[j], a[i]); //Swap with leftmost element bigger than pivot, i.e. v[i] 
     i++; 
     } 

    } 
    //Now pivot needs to go to its proper place 
    swap(a[l], a[i - 1]); 

    return ppos; //WRONG, will return l always, need to return i-1 

    } 
    void quickSort(vector<int64>& a, int l, int r) //Inplace so no return stuff 
    { 
    if(r - l <= 0) 
     return ; 



    int pivotPosition = partitionAroundPivot(a, l, r); 
    cout << "Called Qsort with positions l " <<l << " r " << r << " Pivot pos " << pivotPosition << endl; 

    for (int i = l; i < r; i++) 
     cout << a[i] <<" " ; 

    cout << endl; 
    quickSort(a, l    , pivotPosition - 1); 
    quickSort(a, pivotPosition + 1 , r    ); 

} 

int main() { 

vector<int64> x = {3, 2, 1, 8, 6, 7, 6, 4}; 
quickSort(x, 0, x.size() -1); 

return 0; 
} 

一部は以下の通りです：

Called Qsort with positions l 0 r 9 Pivot pos 0 
1 2 3 4 6 10 9 5 7 
Pivot: 2 
Called Qsort with positions l 1 r 9 Pivot pos 1 
2 3 4 6 10 9 5 7 
Pivot: 3 

編集：私は、合計theoriticallyで行われた比較の数を計算することになっていますので、私はこれだった尋ねた理由の一部実際には比較の一部しか実際には起こらないので、実際には異なっていると思います（各パーティション呼び出し-1でサブアレイのサイズを値として使用します）。これは上記のnumberOfComparisons変数にあります。

ここでは100個の数字をすべて1から100にソートするために、ユニークでほとんどランダムではなく、計算の数が4851、100 * 99/2に近いn *（n-1 ）/ 2ここでn = 100。これはO（n^2）時間を過ごしていると私に信じさせました。これは正しいです...？

EDIT2：結局、私はとてもばかげていました。 partitionAroundPivotは常に、サブ配列の最初の位置を返していました。その結果、分割の1つが長さゼロの部分配列で、残りの部分が配列の残りの部分になりました。私は[l]が実際に行く位置を返す必要があります。 i-1とする。レッスンは学んだと思います。

大変ありがとうございました！

Answer 1

QucksortはO（n log n）ですが、平均では、最悪の場合はO（n^2）、最良の場合はO（nlogn）です。優れた効率を得るための最も重要な点は、優れたピボットを選択することです。

プログラムでは、最悪のピボットの1つを選択しました。最初または最後のベクトルを選択すると、順序付き（または逆順に並べ替えられた）ベクトルの場合、アルゴリズムは最悪の場合の効率になります。

これはピボットを選択するアルゴリズムについて考える必要がある理由です。最もよく使用される方法の1つは、3つの中央値、例えば、第1、中間および最後の要素を選択することである。したがって、順序付きベクトルに適用されるアルゴリズムはO（nlogn）です。

更新：複雑さは、特定のケースではなく、成長のプロファイルによって決まります。実際には、問題のサイズが非常に大きくなると、プロファイルがよりスムーズに増加する一方で、問題の特定のサイズに対して非常に高い価値を持つことができます。何かを調べる前に、いくつかの個々の値が非常に大きいnに達するようにプログラムを実行してください。