Comptage du nombre de comparaisons effectuées dans Heapsort

Question

J'essaie de compter le nombre de comparaisons effectuées par l'algorithme de tri de tas. mon code est basé sur la file d'attente prioritaire et je veux savoir où je devrais mettre le compteur. Voici ce que j'ai, mais quand j'essaie d'imprimer le compteur, il montre zéro compte, qu'est-ce que je fais mal? Je vous remercie.

ici est la fonction heapbuild:

#include<iostream> 

vector<int> pq_keys; 
void buildHeap() 
{ 
int size = pq_keys.size(); 
int midIdx = (size -2)/2; 
while (midIdx >= 0) 
{  
    shiftRight(midIdx, size-1);  
    --midIdx; 
} 

et c'est la fonction qui fait la comparaison:

int shiftRight(int low, int high) 
{ 
    int root = low; 
    int counter=0; 
    while ((root*2)+1 <= high) 
    { 
     int leftChild = (root * 2) + 1; 
     int rightChild = leftChild + 1; 
     int swapIdx = root; 
     if (pq_keys[swapIdx] < pq_keys[leftChild]) 
    { 
     counter++; 
     cout<<counter; 
     swapIdx = leftChild; 

    } 
    /*If right child exists check if it is less than current root*/ 
    if ((rightChild <= high) && (pq_keys[swapIdx] < pq_keys[rightChild])) 
    { 
    counter++; 
    swapIdx = rightChild;  
    } 
    /*Make the biggest element of root, left and right child the root*/ 
    if (swapIdx != root) 
    { 
    counter++; 
    int tmp = pq_keys[root]; 
    pq_keys[root] = pq_keys[swapIdx]; 
    pq_keys[swapIdx] = tmp; 
    root = swapIdx; 
    } 
    else 
    { 
     break; 
    } 
} 

return counter; 

} 

Answer 1

Vous voulez incrémenter le compteur avant que vous faites la comparaison . Considérez ce code, à partir de votre méthode shiftRight:

if (pq_keys[swapIdx] < pq_keys[leftChild]) 
{ 
    counter++; 
    cout<<counter; 
    swapIdx = leftChild; 

} 

Ce incrémente le compteur si la condition est vraie. Si pq_keys[swpIdx] >= pq_keys[leftChild], alors vous avez fait la comparaison sans le compter. Vous devez changer votre code pour être:

counter++; 
if (pq_keys[swapIdx] < pq_keys[leftChild]) 
{ 
    cout<<counter; 
    swapIdx = leftChild; 

} 

Vous devez faire la même chose dans les deux autres endroits où vous comptez des comparaisons: incrémenter le compteur, puis faire la comparaison.

Answer 2

class LessPredicate 
{ 
    size_t callCount_ = 0; 

    temlate<class T> 
    bool compare(const T& l, conct T& r) 
    { 
    return l < r; // or other logic 
    } 
public: 
    size_t CallTimes() const { return callCount_; } 
    temlate<class T> 
    bool operator() (const T& l, conct T& r) 
    { 
    ++callCount_; 
    return compare(l, r); 
    } 
}; 



    int main() 
    { 
    LessPredicate less; 
    ...// use it like less(a, b) instead a < b; 
    auto compareCount = less.CallTimes(); 
    }