I have this program, how can I put a counter to count the number of comparisons
ID: 3799936 • Letter: I
Question
I have this program, how can I put a counter to count the number of comparisons and how can I put a cout statement to print out the number of comparisons?
thank you
#include <iostream>
using namespace std;
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.
*/
void merge(int theArray[], int first, int mid, int last)
{
//cout<<"In merge" <<endl;
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++;
comparisons++;
}
else
{
tempArray[index] = theArray[first2];
first2++;
} //end if
index++;
} //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++;
comparisons++;
}//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++;
comparisons++;
}//end for
//copy the result back into the original array
for(index = first; index <=last; index++)
{
theArray[index] = tempArray[index];
comparisons++;
}
} // end merge
/*
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<<endl;
//sort right half theArray[mid+1..last]
mergeSort(theArray, mid+1, last);
//cout<<"first in the right: " <<first <<endl;
//merge the two halves
merge(theArray, first, mid, last);
}//end if
} //end mergeSort
void displayArray(int theArray[], int size)
{
for(int i=0; i <size; i++ )
{
cout<<theArray[i]<<" ";
}//end for
}// end displayArray
int main()
{
int data[] = {1};
//int data1[] = {2, 1};
//int data2[] ={ 1,2};
int data3[] = {7, 2, 5, 6, 1, 0};
cout<<"The array data contains: " << endl;
displayArray(data,1);
cout<<endl;
mergeSort(data,0,0); // the int is the size of the
cout<<endl;
cout<< "The array data after sorting: " << endl;
displayArray(data,1);
cout<<endl<<endl;
cout<<"The array data3 contains: " << endl;
displayArray(data3,6);
cout<<endl;
mergeSort(data3,0,5);
cout<<endl;
cout<< "The array data3 after sorting: " << endl;
displayArray(data3,6);
cout<<endl;
}
Explanation / Answer
You can use comparisons variable as global variable,
eg:
#include <iostream>
using namespace std;
const int MAX_SIZE = 300;
int comparisons = 0; //-- global variable declaration.
....
and remove it from merge method,
....
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; -- here i have commentted. you can remove it from code
.....
You need to count all type of comapre action, even else case (if you wish then you can modify it), so..
....
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++;
comparisons++; //- remove this one
}
else
{
tempArray[index] = theArray[first2];
first2++;
} //end if
index++;
}
......
change it like as below,
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++; //-- added here
}
remaining as it is.
And then add new method named as setComparisons under displayArray method. In order to initialize comparisons variable to each and every mergeSort call,
....
void setComparisons()
{
comparisons = 0;
}
....
finally you can modify main method as like below,
int main()
{
int data[] = {1};
//int data1[] = {2, 1};
//int data2[] ={ 1,2};
int data3[] = {7, 2, 5, 6, 1, 0};
cout<<"The array data contains: " << endl;
displayArray(data,1);
cout<<endl;
setComparisons();//-- initialize comparisons variable before mergeSort call made
mergeSort(data,0,0); // the int is the size of the
cout<<endl;
cout<< "The array data after sorting: " << endl;
displayArray(data,1);
cout<<endl;
cout << "Total Number of Comparisons : " << comparisons << " ";
cout<<"The array data3 contains: " << endl;
displayArray(data3,6);
cout<<endl;
setComparisons();//-- initialize comparisons variable before mergeSort call made
mergeSort(data3,0,5);
cout<<endl;
cout<< "The array data3 after sorting: " << endl;
displayArray(data3,6);
cout<<endl;
cout << "Total Number of Comparisons : " << comparisons << " ";
}