5. The goal of this step is to create a class of Integer objects that count how

Question

5. The goal of this step is to create a class of Integer objects that count how many times they are compared or copied. This will allow you (in the next step) to measure the performance of sorting algorithms by observing how many times they compare or copy elements. Whenelements are large, these are the most expensive operations performed by the algorithms. The Integer objects will allow you to count these operations without having to modify the sorting algorithms. You can do this step in one of two ways, as described below The original way is the one that was in the first version of this project description. De- pending on the standard library implementation that your compiler uses, it may give you compilation problems. The preferred way avoids those problems. As a bonus, it also gives you more accurate results. (Because it allows you to count operations performed on all Integer objects, in cluding temporary objects created by the sorting algorithms. The original way only allows you to retrieve the number of operations performed on Integer objects you create yourself) Do this step the preferred way unless you had already done it the original way and didn't have compilation problems

Explanation / Answer

#include<iostream>
#include <cstdlib>
using namespace std;
//Global variable
int Integer_count = 0;
//Integer class definition
class Integer
{
//Data member
int data;
public:
//Default constructor
Integer()
{
data = 0;
}
//Parameterized constructor
Integer(int x)
{
data = x;
}
//Copy constructor
Integer(Integer &a)
{
data = a.data;
Integer_count++;
}
//Set data function
void setData(int n)
{
data = n;
Integer_count++;
}
//Return value
int value()
{
return data;
}
//Overloading less than operator
friend bool operator < (const Integer i1, const Integer i2)
{
Integer_count++;
if(i1.data < i2.data)
return true;
else
return false;
}
//Overload equals operator
Integer operator = (Integer i2)
{
Integer_count++;
data = i2.data;
}
//Displays data
void disp()
{
cout<<" data = "<<data;
}
};//End of class

//Function to quick sort
template <class T>
void quicksort(T a[], int start, int stop)
{
if(stop - start > 1)
{
int pivot = start + rand() % (stop - start);
partition(a, start, stop, pivot);
quicksort(a, start, pivot);
quicksort(a, pivot + 1, stop);
}
}
//Function to partition
template<class T>
int partition(T a[], int start, int stop, int &pivot)
{
std::swap(a[pivot], a[start]);
T *temp = new T[stop - start];
int k = 0;
for(int i = start + 1; i < stop; ++i)
if(a[i] < a[start])
{
temp[k] = a[i];
++k;
}
temp[k] = a[start];
pivot = start + k;
++k;
for(int i = start + 1; i < stop; ++i)
{
if(!(a[i] < a[start]))
{
temp[k] = a[i];
++k;
}
}
std::copy(temp, temp + k, a + start);
delete temp;
}
//Main function
int main()
{
//Declares an array of object
Integer N[50];
int x, no;
//Accepts the size of array
cout<<" Enter the size of array: ";
cin>>no;
//Accepts data
cout<<" Enter "<<no<<" numbers: ";
for(int i = 0; i < 5; i++)
{
cin>>x;
N[i].setData(x);
}

cout<<" Before Sorting: ";
for(int i = 0; i < 5; i++)
N[i].disp();

quicksort(N, 0, 5);
cout<<" After Sorting: ";
for(int i = 0; i < 5; i++)
N[i].disp();
cout<<" Number of compares : "<<Integer_count;
}//End of main

Output:

Enter the size of array: 6

Enter 6 numbers: 12
10
23
45
5

Before Sorting:

data = 12
data = 10
data = 23
data = 45
data = 5
After Sorting:

data = 5
data = 10
data = 12
data = 23
data = 45
Number of compares : 102

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.