クイックソートアルゴリズムの基本操作の計算

Question

Hoareのクイックソートアルゴリズムによって行われる基本操作の数を数えようとしています。カウンターを正しい位置に置いたのかどうか疑問に思っています。私の割り当ては、10,100,1k、および10kのサイズのランダムに生成された100個の配列に対する基本操作の数を数えることです。ここで

は、カウンターに置い（ライン6）とアルゴリズムです：

void QuickSort(int* array, int startIndex, int endIndex, int &counter) { 
    int pivot = array[startIndex];     //pivot element is the leftmost element 
    int splitPoint; 

    if (endIndex > startIndex)                      
    { 
     counter++; //counting 
     splitPoint = SplitArray(array, pivot, startIndex, endIndex); 
     array[splitPoint] = pivot; 
     QuickSort(array, startIndex, splitPoint - 1, counter); //Quick sort first half 
     QuickSort(array, splitPoint + 1, endIndex, counter);  //Quick sort second half 
    } 
} 
void swap(int &a, int &b) { 
    int temp; 
    temp = a; 
    a = b; 
    b = temp; 
} 
int SplitArray(int* array, int pivot, int startIndex, int endIndex) { 
    int leftBoundary = startIndex; 
    int rightBoundary = endIndex; 

    while (leftBoundary < rightBoundary)    
    { 
     while (pivot < array[rightBoundary]  
      && rightBoundary > leftBoundary)  
     { 
      rightBoundary--;       
     } 
     swap(array[leftBoundary], array[rightBoundary]); 


     while (pivot >= array[leftBoundary]  
      && leftBoundary < rightBoundary)  
     { 
      leftBoundary++;      
     } 
     swap(array[rightBoundary], array[leftBoundary]);    
    } 
    return leftBoundary;        

} 

これらの結果は意味をなさないか？

Array[Amount] Array[10]  Array[100]  Array[1k]  Array[10k] 
MAX:     8    72    682  7122 
MIN:     5    63    653  7015 
AVERAGE:    6.36   66.54   667.87  7059.41 

または、私は間違った場所にカウンターを置きましたか？

Answer 1

カウンタの位置が間違っています。あなたの割り当ては、基本的な操作を数えることです。ソートの基本操作は何ですか？通常、我々はの数を数えての演算と比較し、並べ替えの複雑さを測定する。

クイックソートは平均でO（N Log N）であり、Nはソートされるアイテムの数であり、最悪の場合はO（N^2）であることがわかります。

あなたの数字は、N個のアイテムのそれぞれが少なくとも1回は他のアイテムと比較されなければならないので不可能です。ソートのコストはN未満でなければなりません。そうでなければ、何かに、それはソートされていることを保証することはできませんでした）。

アルゴリズムでは、配列の要素をピボット値と比較するときに比較演算が行われます。配列要素をPivotと比較するたびにカウンターをインクリメントしてください。あなたの測定数は少なくともNでなければならず、通常N * log N程度であり、まれにN^2に近いことはほとんどありません。

SplitArrayでどこカウンタをインクリメントするには、以下の提案のポイントを参照してください。

void swap(int &a, int &b) { 
    int temp; 
    temp = a; 
    a = b; 
    b = temp; 
} 

SplitArrayは比較を行い、そのカウンタは、ここでインクリメントする必要があります。

void QuickSort(int* array, int startIndex, int endIndex, int &counter) { 
    int pivot = array[startIndex];     //pivot element is the leftmost element 
    int splitPoint; 

    if (endIndex > startIndex)                      
    { 
     // counter++; // Don't count here 
     splitPoint=SplitArray(array, pivot, startIndex, endIndex, counter); 
     array[splitPoint] = pivot; 
     QuickSort(array, startIndex, splitPoint - 1, counter); //Quick sort first half 
     QuickSort(array, splitPoint + 1, endIndex, counter);  //Quick sort second half 
    } 
} 

変更なしには交換します：

int SplitArray(int* array,int pivot,int startIndex,int endIndex,int &counter) { 
     int leftBoundary = startIndex; 
     int rightBoundary = endIndex; 

    while ((++counter) && (leftBoundary < rightBoundary))    
    { 
     while (pivot < array[rightBoundary]  
      && rightBoundary > leftBoundary)  
     { 
      rightBoundary--;       
     } 
     swap(array[leftBoundary], array[rightBoundary]); 


     while ((++counter) && (pivot >= array[leftBoundary])  
      && leftBoundary < rightBoundary)  
     { 
      leftBoundary++;      
     } 
     swap(array[rightBoundary], array[leftBoundary]);    
    } 
    return leftBoundary;        

}