マージソートアルゴリズムのカウントスワップ/比較数の数値

Question

マージソート中にスワップと比較が何回起こったのかをカウントする必要があります。私の比較数は問題ないと思います。これらの数値をマージソート関数で変数に格納する必要があるかどうかを確認することもできます。

void merge(double arr[], int l, int m, int r) 
    { 
     int counter = 0;//number of comparisons 
     int i, j, k; 
     int n1 = m - l + 1; 
     int n2 = r - m; 
     int cc; 
     /* create temp arrays */ 
     double L[n1], R[n2]; 
     /* Copy data to temp arrays L[] and R[] */ 
     for (i = 0; i < n1; i++) 
      L[i] = arr[l + i]; 
     for (j = 0; j < n2; j++) 
      R[j] = arr[m + 1+ j]; 
     /* Merge the temp arrays back into arr[l..r]*/ 
     i = 0; // Initial index of first subarray 
     j = 0; // Initial index of second subarray 
     k = l; // Initial index of merged subarray 
     while (i < n1 && j < n2) 
      { 

       if (L[i] <= R[j]) 
       { 
        arr[k] = L[i]; 
        i++; 
       } 
       else 
       { 
        arr[k] = R[j]; 
        j++; 
       } 
       k++; 
       counter++; 
     } 
     cout << counter << endl; 
    /* Copy the remaining elements of L[], if there 
     are any */ 
     while (i < n1) 
     { 
      arr[k] = L[i]; 
      i++; 
      k++; 
     } 
    /* Copy the remaining elements of R[], if there 
     are any */ 
     while (j < n2) 
     { 
      arr[k] = R[j]; 
      j++; 
      k++; 
       } 
    } 
    void mergeSort(double arr[], int l, int r) 
     { 
      if (l < r) 
     { 
      // Same as (l+r)/2, but avoids overflow for 
     // large l and h 
     int m = l+(r-l)/2; 
     // Sort first and second halves 
     mergeSort(arr, l, m); 
     mergeSort(arr, m+1, r); 
     merge(arr, l, m, r); 
     } 
    } 

Answer 1

これは@JerryCoffinによって与えられた答えに似ていますが、あなたが消化するために多分少し単純。

単純な解決策は、このコードをクラスに配置し、各スワップが実行されるごとにインクリメントするメンバ変数（int swapcountと呼ばれることもあります）を持つことです。これにより、ローカルスワップカウンタ変数を維持する必要がなくなります。

class MergeSorter 
{ 
    int swapCount; 
    void merge(double arr[], int l, int m, int r); 
    void mergeSort(double arr[], int l, int r); 

    public: 
     MergeSorter() : swapCount(0) { } 
     void startSort(double arr[], int l, int r); 
     int getSwapCount() const { return swapCount; } 
}; 

void MergeSorter::merge(double arr[], int l, int m, int r) 
{ 
    // code here to merge. In here, you increment swapCount 
} 

void MergeSorter::mergeSort(double arr[], int l, int r) 
{ 
    if (l < r) 
    { 
     int m = l+(r-l)/2; 
     mergeSort(arr, l, m); 
     mergeSort(arr, m+1, r); 
     merge(arr, l, m, r); 
    }  
} 

void MergeSorter::startSort(double arr[], int l, int r) 
{ 
    swapCount = 0; // start at 0 
    mergeSort(arr, l, r); 
} 

int main() 
{ 
    double arr[] = {1, 2, 3, 45, 5, 7}; 
    MergeSorter ms; 
    ms.startSort(arr, 0, 5); // or whatever the arguments are 
    std::cout << "The number of swaps is " << ms.getSwapCount(); 
} 

クラス内でソートを開始する関数startSortがあります。 merge機能では、必要に応じてswapCountがインクリメントされます。最後に、ms.swapCountという値を出力します。

Answer 2

私は仕事をやや異なった方法で行います。

ソート自体を計測して数や比較やスワップを計測するのではなく、比較やスワップの回数を記録する型を作成します。私はそれを証明するために全体のマージソートを書くのが面倒だったが、ここではバブルソートやっ一つです。これで、あなたは（たとえば）std::sortの結果を得ることができる必要がありますことを

#include <algorithm> 
#include <iostream> 
#include <vector> 

namespace instrumented { 

    template <class T> 
    class wrapper { 
     T value; 
    public: 
     static std::size_t comparisons; 
     static std::size_t swaps; 
     wrapper(T val) : value(val) {} 
     bool operator<(wrapper const &other) { ++comparisons; return value < other.value; } 
     operator T() const { return value; } 

     static void reset() { comparisons = swaps = 0; } 

     static std::ostream &report(std::ostream &os) { 
      os << "comparisons: " << comparisons << "\n"; 
      os << "swaps: " << swaps << "\n"; 
      comparisons = 0; 
      swaps = 0; 
      return os; 
     } 
    }; 

    template <class T> 
    std::size_t wrapper<T>::comparisons; 

    template <class T> 
    std::size_t wrapper<T>::swaps; 

    template <class T> 
    void swap(wrapper<T> &a, wrapper<T> &b) { 
     ++wrapper<T>::swaps; 
     auto temp{ a }; 
     a = b; 
     b = temp; 
    } 
} 

template <class T> 
void sort(std::vector<T> &input) { 
    std::vector<instrumented::wrapper<T>> values; 

    for (auto const & i : input) 
     values.push_back(i); 

    for (auto i = 0; i < values.size() - 1; i++) 
     for (auto j = i + 1; j < values.size(); j++) 
      if (values[j] < values[i]) 
       swap(values[i], values[j]); 

    values[0].report(std::cout); 
} 

int main() { 
    std::vector<int> inputs1{ 5, 4, 3, 2, 1 }; 
    sort(inputs1); 
    std::cout << "\n"; 

    std::vector<int> inputs2{ 10, 9, 7, 8, 5, 100, 2, 3, 1, 17, 6 }; 
    sort(inputs2); 
} 

注、std::partial_sortは、自分のソート関数だけでなく、順番に並べ替えます。

Answer 3

私が正しく理解していれば、元の配列がマージステップで変更されたときにスワップが発生します。したがって、マージの各呼び出しでは、元のインデックスの値を調べ、そのインデックスに対応する新しく形成された値と比較します。彼らが違うなら、私はスワップを増やした。

int swap=0; 

int index(std::vector<double> v,double val){ 

auto match = std::find(v.begin(), v.end(), val); 
return match-v.begin(); 

} 

std::vector<double> merge(std::vector<double> v1,std::vector<double> v2,std::vector<double>& v,int start){ 

auto it1=std::begin(v1); 
auto it2=std::begin(v2); 

std::vector<double> newvec; 

while(it1!=v1.end() && it2!=v2.end()){ 

    if(*it1<=*it2){ 

     newvec.push_back(*it1); 

     const FloatingPoint<double> l1(*it1), r1(v.at(index(newvec,*it1)+start)); 

     if (!l1.AlmostEquals(r1)) swap++; 

     it1++; 

    } 

    else{ 

     newvec.push_back(*it2); 

     const FloatingPoint<double> l2(*it2), r2(v.at(index(newvec,*it2)+start)); 

     if (!l1.AlmostEquals(r1)) swap++; 

     it2++; 

    } 

} 

while(it1!=v1.end()){ 

    newvec.push_back(*(it1++)); 

    const FloatingPoint<double> l3(*it1), r3(v.at(index(newvec,*it1)+start)); 

    if (!l3.AlmostEquals(r3)) swap++; 

} 

while(it2!=v2.end()){ 

    newvec.push_back(*(it2++)); 

    const FloatingPoint<double> l4(*it2), r4(v.at(index(newvec,*it2)+start)); 

    if (!l4.AlmostEquals(r4)) swap++; 


} 

return newvec; 

} 


std::vector<double> merge_sort(std::vector<double> v,int start){ // start=0 when it is first called 

int size=v.size(); 

if(size==1) return v; 

std::vector<double> merged1,merged2; 

auto it=v.begin(); 

merged1.assign(it,it+(size+1)/2); 
merged2.assign(it+(size+1)/2,v.end()); 

std::vector<double> v1=merge_sort(merged1,start); 
std::vector<double> v2=merge_sort(merged2,start+(size+1)/2); 

v=merge(v1,v2,v,start); 

return v; 

}