Write a C++ program called performance.cpp that displays the performance of two

Question

Write a C++ program called performance.cpp that displays the performance of two different sorting algorithms (= selection sort and quick sort) on the screen.

For the problem, your program should read the input size (= number of input data) and max value of input data from a user. In the program, you should generate the input data (= integer numbers) using a random number generator. The random numbers generated by your program should be in the range between zero and the max value given by the user. For the homework, your program should save the input data to a file called “input.txt” so that you can check the content of the input data later when you finish the execution.

Once your program generates the input data, it should conduct two sorting algorithms for the input file and display the number of execution of the basic operation in the algorithms. In the case of the two algorithms, a comparison operation will be the basic operation of each algorithm.

For the homework, you have to use dynamic array(s) to process the sorting data and the pseudocode covered in the textbook. The selection sort is described in the page 99 and the quicksort is presented in Chapter 5.2.

The following presents a sample run of the program. Your program should run like this.

Enter input size: 3000

Enter max value of input: 5

============================================================

Generate input data . . .

Done.

============================================================

Selection sort performance

Number of executions: ???? times

============================================================

Quicksort performance

Number of executions: ???? times

============================================================

In the sample execution, your program should generate 3,000 integer numbers in the file input.txt. The data in the file should have integer values between 0 and 5 because the user entered 5 as the max value of the input data. This is a sample content of the file:

0 5 3 3 2 0 5 ... // It should have total 3,000 numbers.

In the sample execution, the instructor presents the number of executions as “???? times”. But in your real execution, your program should present an actual number such as “23519 times”.

For the homework, it’s enough to display the number of executions of the basic operation in each algorithm. Originally, the instructor considered to display “elapsed time” of each program. However, the time measurement depends on the OS and machine you use. Thus, the instructor decided to display the number of executions of the basic operation using a counter.

Explanation / Answer

#include <cstdlib>
#include <ctime>
#include <iostream>
#include<fstream>
using namespace std;

void selectsort (int [], int);
void quicksort(int[],int,int);
int part(int[],int,int);
int d,c;

//Driver Function
int main ()
{
int size;
cout<< "how big do you want the array?" << endl;
cin >> size;
int ar[size];
srand((unsigned)time(0));
for(int i=0; i<size; i++)
{
ar[i] = (rand()%5)+1; // storing the random numbers in the array
}
  
ofstream fout("input.txt"); //opening file input.txt
   if(fout.is_open()) //if file there
   {
  
cout << "Generate input Data" << endl;
cout<<" Done "<<endl;

       for(int i = 0; ar[i] != ''; i++)
       {
fout << ar[i]; //storing the data into the file
}
   }
   else //file could not be opened
   {
       cout << "File could not be opened." << endl;
   }
  
selectsort (ar,size); //caling the selection sort function
cout << "Selection sort Performance : "<<endl;
cout<<"Number of steps :"<<c<<endl;
quicksort(ar,0,size-1); //calling the quick sort function
cout << "Selection sort Performance : "<<endl;
cout<<"Number of steps :"<<d<<endl;
  
return 0;
}

void quicksort(int a[],int h,int p)
{
int k;
if(h<p)
{   
k=part(a,h,p);
quicksort(a,h,k-1);
quicksort(a,k+1,p);
d=d+1;
}
  
}

int part(int a[],int h,int p)
{
int x,i,j,t;
x=a[h];
i=h;
j=p+1;
  
do
{
do
i++;
  
while(a[i]<x&&i<=p);
  
do
j--;
while(x<a[j]);
  
if(i<j)
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}while(i<j);
  
a[h]=a[j];
a[j]=x;
  
return(j);
}

// Selection Sort
void selectsort(int arr[], int n)
{

   int min,t;

   for (int i=0; i < n-1; i++)
   {
   min = i;
      
       for (int j=i+1; j < n; j++)
       {

       if (arr[j] < arr[min])
min=j;
  
       }
      
  
if (min != i)
{
t= arr[i];
arr[i] = arr[min];
arr[min] = t;
}
c=c+1;
   }
   //cout<<"Number of steps"<<c<<" ";
  
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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