I have this merge sort. I need to add a counter to check the comparisons. In ord
ID: 3800668 • Letter: I
Question
I have this merge sort. I need to add a counter to check the comparisons. In order words, how often I check one element in the array against another?
Am I doing it, right? If not, How can I fix it? Thank you
#include
using namespace std;
int comparisons = 0; //-- global variable declaration.
const int MAX_SIZE = 300;
/*
Merges two sorted array segments theArray[first..mid] and
theArray[mid+1..last] into one sorted array.
@pre first<=m mid <= last. The subarrays theArray[first..mid] and
theArray[mid+1..last] are each sorted in inceasing order.
@post theArray[first..last] is sorted.
@param theArray: the given array
@param first: the index of the beginning of the first segmet in theArray
@param mid: the index of the end of the first segment in theArray;
mid+1: marks the beginning of the second segment.
@param: last: the index of the last element in the second segment in theArray.
@note: this function merges the two subarrays into a temporary array
and copies the result into the original array theArray.
*/
int merge(int theArray[], int first, int mid, int last)
{
//cout<<"In merge" < int tempArray[MAX_SIZE]; //temparay array
int first1 = first; //beginning of first subarray
int last1 = mid; //end of first subarray
int first2 = mid+1; // beginning of second subarray
int last2 = last; // end of second subarray
//int comparisons =0;
//while noth subarrays are not empty, copy the
//smaller item into the temporary array
int index = first1; //next available location in temArray
while((first1<=last1) && (first2<=last2))
{
//At this point, temArray[first..index-1] is in order
if(theArray[first1] <= theArray[first2])
{
tempArray[index] = theArray[first1];
first1++;
}
else
{
tempArray[index] = theArray[first2];
first2++;
} //end if
index++;
comparisons++; //compare here
} //end while
//finish off the first subarray, if necessary
while(first1 <= last1)
{
//at this point, temArray[first..index-1] is in order
tempArray[index] = theArray[first1];
first1++;
index++;
//comparison++
}//end while
//finish off the second subarray if necessary
while(first2<=last2)
{
//at this point, temArray[first..index-1] is in order
tempArray[index] = theArray[first2];
first2++;
index++;
//comparison++
}//end for
//cout <<"number of comparisons " << comparisons <
//copy the result back into the original array
for(index = first; index <=last; index++)
{
theArray[index] = tempArray[index];
}
return comparisons;
} // end merge
void setComparisons()
{
comparisons = 0;
}
/*
Sorts the items in an array into ascending order.
@pre theArray[first..last] is an array.
@post theArray[first..last] is sorted in ascending order.
@param theArray: the given array.
@param first: the index o the first element to consider in theArray.
@param last: the index of the last element to consider in theArray.
*/
void mergeSort(int theArray[], int first, int last)
{
if(first < last)
{
// sort each half
int mid = first+ (last-first)/2;
// sort left half theArray[first..mid]
mergeSort(theArray, first, mid);
//cout <<"first in the left: " << first< //sort right half theArray[mid+1..last]
mergeSort(theArray, mid+1, last);
//cout<<"first in the right: " <
//merge the two halves
merge(theArray, first, mid, last);
}//end if
} //end mergeSort
void displayArray(int theArray[], int size)
{
for(int i=0; i {
cout<
int main()
{
int data[] = {1};
int data1[] = {2, 1};
int data2[] ={ 1,2,3};
int data3[] = {7, 2, 5, 6, 1, 0};
cout<<"The array data contains: " << endl;
displayArray(data,1);
cout< setComparisons();//-- initialize comparisons variable before mergeSort call made
mergeSort(data,0,0); // the int is the size of the
cout<< "The array data after sorting: " << endl;
displayArray(data,1);
cout< cout << "Total Number of Comparisons : " << comparisons << endl<
cout<<"The array data3 contains: " << endl;
displayArray(data3,6);
cout< setComparisons();//-- initialize comparisons variable before mergeSort call made
mergeSort(data3,0,5);
cout<< "The array data3 after sorting: " << endl;
displayArray(data3,6);
cout< cout << "Total Number of Comparisons : " << comparisons << endl<
cout<<"The array data2 contains: " << endl;
displayArray(data2,3);
cout< setComparisons();//-- initialize comparisons variable before mergeSort call made
mergeSort(data2,0,);
cout<< "The array data after sorting: " << endl;
displayArray(data2,3);
cout< cout << "Total Number of Comparisons : " << comparisons << endl<
cout<<"The array data1 contains: " << endl;
displayArray(data1,2);
cout< setComparisons();//-- initialize comparisons variable before mergeSort call made
mergeSort(data1,0,1);
cout<< "The array data1 after sorting: " << endl;
displayArray(data1,2);
cout< cout << "Total Number of Comparisons : " << comparisons << endl<
}
Explanation / Answer
Please find the C++ program to count the number of comparisons in merge sorting.
#include <iostream>
#include <stdio.h>
using namespace std;
int counter = 0; //count of comparisons
int n = 0;
const int MAX = 100;
void merging(int values[], int lf, int ll, int rf, int rl);
void print( int a[], int n);
void mergesort(int a[], int begin, int end){
if(begin < end){
int mid = (begin+end)/2;
mergesort(a,begin, mid);
mergesort(a,mid+1,end);
merging(a, begin,mid, mid+1, end);
}
}
void merging(int values[], int lf, int ll, int rf, int rl){
int temparray[MAX];
int index = lf;
int save = lf;
while((lf <= ll) && ( rf <= rl)){
if(values[lf] < values[rf]){
temparray[index] = values[lf];
lf++;
}
else
{
temparray[index] = values[rf];
rf++;
}
index++;
counter++;
}
while(lf <= ll){
temparray[index] = values[lf];
lf++;
index++;
}
while(rf <= rl){
temparray[index] = values[rf];
rf++;
index++;
}
for(index = save; index <= rl; index++)
values[index] = temparray[index];
print(values,n);
cout << endl;
}
void print( int a[], int n){
for (int i=0; i < n; i++)
cout << a[i] << " ";
}
int main(){
cout << "Enter number of elements to sort : ";
cin >>n;
int a[MAX];
for (int i=0; i < n; i++){
if(i==0)
cout << "Enter the first element: ";
else
cout << "Enter the next element: ";
cin >> a[i];
}
int begin = 0;
int end = n-1;
mergesort(a, begin, end);
print(a, n);
cout << endl;
cout << "Number of comparisons : "<< counter << endl;
}
Output: