マージソートを使った計算の比較

Question

今はアルゴリズムについて学んでいます。さまざまなソート方法に戻って、各種類の数値を並べ替えるために各種類の比較を調べることをおすすめしました。このMerge Sortプログラムの内部でカウントを実装する必要がありますが、どこに行く必要があるか分からなくなっています。誰かが私を正しい方向に向けることができれば、本当に感謝しています。

//MergeSort.h 

#include <iostream> 
using namespace std; 
void merge_sort(int A[], int low, int high); 
void merge(int A[], int low, int mid, int high); 

void merge_sort(int A[], int low, int high) 
{ 
    int mid; 
    if(low<high) 
    { 
     mid=(low+high)/2; 
     merge_sort(A,low,mid); 
     merge_sort(A,mid+1,high); 
     merge(A,low,mid,high); 

    } 
} 

void merge(int A[], int low, int mid, int high) 
{ 
    int h, i, j, B[100], k; 
    h = low; 
    i = low; 
    j = mid + 1; 

    while ((h <= mid) && (j <= high)) 
    { 
     if (A[h] <= A[j]) 
     { 
      B[i] = A[h]; 
      h++; 
     } 
     else 
     { 
      B[i] = A[j]; 
      j++; 
     } 
     i++; 
    } 

    if (h > mid) 
    { 
     for (k = j;k <= high;k++) 
     { 
      B[i] = A[k]; 
      i++; 
     } 
    } 
    else 
    { 
     for (k = h;k <= mid;k++) 
     { 
      B[i] = A[k]; 
      i++; 
     } 
    } 

    for (k = low;k <= high;k++) 
    { 
     A[k] = B[k]; 
    } 
} 

と

//MergeSort.cpp 

#include <iostream> 
using namespace std; 

#include "MergeSort.h" 
#include <ctime> 

int main() 
{ 
    int A[1000], n = 100, i; 
    srand(time(NULL)); 

    cout << "Here are " << n << " random numbers: \n"; 
    for (i = 0; i < n; i++) 
    { 
     A[i] = rand() % 100; 
     cout << " " << A[i]; 
    } 

    merge_sort(A, 0, n-1); 

    cout << "\n\nThe sorted array is: "; 
    for (int i=0;i<n;i++) 
     cout << A[i] <<" "; 

    cout<<endl<<endl; 
    system("pause"); 
} 

Answer 1

比較回数を数える簡単な方法の1つは、mergeとmerge-sortの機能をvoidから変更して、それらの中で比較回数を返し、再帰的にカウントすることです。

Answer 2

B「の長さの配列のみ100.itがバインドされています。

Answer 3

これを行う最も簡単な方法は、静的なグローバル変数を使用し、merge（）のA []の各比較でインクリメントしてから、メインプログラムにソート後のカウントを表示させることです。これにより、既存の関数のインタフェースを変更する必要がなくなります。