CODEWITHSUNDEEP
c++algorithmsorting
Nick
Nick

Reputation: 3

Counting Comparisons with Merge Sort

Right now I'm learning about algorithms, and I was encouraged to go back through all the different sorting methods to find out how many comparisons each kind takes to sort through an array of numbers. I need to implement a count inside this Merge Sort program which works, but I'm getting a little lost as far as where it needs to go. If anyone could point me in the right direction, I'd really appreciate it.

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

and 

//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");
}

Upvotes: 0

Views: 1663

Answers (3)

rcgldr
rcgldr

Reputation: 28921

The simplest way to do this is to use a static global variable, and increment it with each compare of A[] in merge(), then have the main program display the count after a sort. This avoids having to change the interface for the existing functions.

Upvotes: 0

Dandelion
Dandelion

Reputation: 756

One simple way to count number of comparisons is to change your merge and merge-sort functions from void to return number of comparisons within them and counting recursively.

Upvotes: 1

Sky
Sky

Reputation: 11

The array of B 's length is only 100.it will be bound.

Upvotes: 0

Related Questions