이 병합 정렬 알고리즘은 얼마나 많은 비교를합니까?

Question

이 알고리즘에 의해 얼마나 많은 비교가 수행되었는지 계산하려면이 코드에 compare++을 추가하고 싶습니다. 의 카운트가 Merge(...)의 첫 번째 while 루프와 while 내부의 if 및 else의 각 실행에서 증가해야합니까? 이것들은 compare이 증가되어야하는 유일한 위치입니까? (나는 내가 속한 및 주석 생각이 증가를 추가했습니다. 스왑 기능을 무시하십시오)

#include "MergeSort.h" 

template<class ItemType> 
void MergeClass<ItemType>::sort(ItemType values[], int first, int last) 
// Post: The elements in values are sorted by key. 
{ 
    if (first < last) 
    { 
     int middle = (first + last)/2; 
     sort(values, first, middle); 
     sort(values, middle + 1, last); 
     Merge(values, first, middle, middle + 1, last); 
    } 
} 

template<class ItemType> 
void MergeClass<ItemType>::Merge(ItemType values[], int leftFirst, int leftLast, 
int rightFirst, int rightLast) 
// Post: values[leftFirst]..values[leftLast] and 
// values[rightFirst]..values[rightLast] have been merged. 
// values[leftFirst]..values[rightLast] are now sorted. 
{ 
    ItemType tempArray[5]; 
    int index = leftFirst; 
    int saveFirst = leftFirst; 
    while ((leftFirst <= leftLast) && (rightFirst <= rightLast)) 
    { 
     if (values[leftFirst] < values[rightFirst]) 
     { 
      tempArray[index] = values[leftFirst]; 
      leftFirst++; 
      //compare++; 
     } 
     else 
     { 
      tempArray[index] = values[rightFirst]; 
      rightFirst++; 
      //compare++; 
     } 
     index++; 
     //compare++; 
    } 
    while (leftFirst <= leftLast) 
    // Copy remaining items from left half. 
    { 
     tempArray[index] = values[leftFirst]; 
     leftFirst++; 
     index++; 
    } 
    while (rightFirst <= rightLast) 
    // Copy remaining items from right half. 
    { 
     tempArray[index] = values[rightFirst]; 
     rightFirst++; 
     index++; 
    } 
    for (index = saveFirst; index <= rightLast; index++) 
     values[index] = tempArray[index]; 
} 


template<class ItemType> 
inline void MergeClass<ItemType>::Swap(ItemType& item1, ItemType& item2) 
// Post: Contents of item1 and item2 have been swapped. 
{ 
    ItemType tempItem; 
    tempItem = item1; 
    item1 = item2; 
    item2 = tempItem; 
} 

template<class ItemType> 
MergeClass<ItemType>::MergeClass() 
{ 
    compare = 0; 
    swap = 0; 
} 
template<class ItemType> 
void MergeClass<ItemType>::sortPreformance() 
{ 
    cout << "Comparisons made: " << compare <<endl; 
    cout << "Swaps made: "<< swap <<endl; 
} 

Answer 1

을이 프로파일에 대해 엄격하게 의미가 있다면, 나는 정렬 클래스의 외부에서 계산 로직을 넣어 것입니다. 당신이 실제 기능과의 비교를 교체하는 경우

#include <iostream> 
#include <algorithm> 
#include <cstdlib> 
using namespace std; 

template<typename T> 
struct CountingItem { 
    CountingItem(const T& val = T()) : val_(val) {} 

    bool operator<(const CountingItem<T>& rhs) const { 
     ++compares; 
     return val_ < rhs.val_; 
    } 

    static size_t compares; 
    static size_t swaps; 
    T val_; 
}; 

template<typename T> 
size_t CountingItem<T>::compares = 0; 
template<typename T> 
size_t CountingItem<T>::swaps = 0; 

template<typename T> 
void swap(CountingItem<T>& a, CountingItem<T>& b) { 
    ++CountingItem<T>::swaps; 
    std::swap(a, b); 
} 

int main() 
{ 
    const size_t num_items = 10000; 
    CountingItem<int> items[num_items]; 
    for(int i = 0; i < num_items; i++) items[i] = rand() % 100; 
    sort(items, items+num_items); 
    cout << "Compares = " << CountingItem<int>::compares << endl; 
    cout << "Swaps = " << CountingItem<int>::swaps << endl; 

    // Reset CountingItem<int>::compares and swaps here if you're running another test 
}