Zählvergleiche mit Merge Sort

Question

Im Moment lerne ich über Algorithmen, und ich wurde ermutigt, durch die verschiedenen Sortiermethoden zu gehen, um herauszufinden, wie viele Vergleiche jede Art braucht, um eine Reihe von Zahlen zu sortieren. Ich muss eine Zählung in diesem Merge-Sort-Programm implementieren, die funktioniert, aber ich bin ein wenig verloren, soweit es gehen muss. Wenn mir jemand in die richtige Richtung zeigen könnte, würde ich es sehr schätzen.

//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]; 
    } 
} 

und

//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

Eine einfache Möglichkeit, Anzahl der Vergleiche zu zählen ist Ihre merge und merge-sort Funktionen von void zu ändern in ihnen zurückzukehren Anzahl von Vergleichen und Zählen rekursiv.

Answer 2

Die Anordnung von B ‚s Länge ist nur 100.it wird gebunden.

Answer 3

Der einfachste Weg, dies zu tun ist, eine statische globale Variable zu verwenden und sie mit jedem Vergleich von A [] in merge() zu inkrementieren, danach muss das Hauptprogramm die Zählung nach einer Sortierung anzeigen. Dadurch wird vermieden, dass die Schnittstelle für die vorhandenen Funktionen geändert werden muss.