개수 스왑/비교 번호 병합 정렬 알고리즘

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(); 
} 

우리는 클래스 내에서 정렬을 시작하는 함수 이 있습니다. merge 함수에서 필요에 따라 swapCount이 증가합니다. 마지막으로 ms.swapCount 값을 출력합니다.

Answer 2

나는이 작업을 다소 다르게 할 것입니다.

숫자 또는 비교 및 ​​스왑을 추적하기 위해 정렬 자체를 계측하는 대신, 비교 및 ​​/ 또는 스왑 된 횟수를 추적하는 형식을 생성합니다. 나는 그것을 입증하는 전체 병합 정렬을 쓸 너무 게으른,하지만 여기에 하나가 버블 정렬하고있다 :이, 당신이 할 수 있어야한다고

#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::sort, 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; 

}