The purpose of the below program is to perform empirical analysis of the followi

Question

The purpose of the below program is to perform empirical analysis of the following sorting algorithms on integer arrays:

1) Selection sort;

2) Insertion sort;

Write a C++ program for obtaining the running or working times of each algorithm for a particular array(Use gethrtime function).Call this function before and after a call to the function implementing a sorting algorithm listed above.

Requirements:

a) Run your functions for the following types of arrays containing 1000, 10000 and 100000 integers: random numbers, sorted list, almost sorted list (say, each 10th number is out of order).

b) The size of integers is supposed to be from 1 to 10000.

Explanation / Answer

here is what you want
#include<iostream>
#include<stdio.h>
#include<sys/time.h>
#include <ctime>
using namespace std;
void selection(int [],int);
void insertion(int [],int);
double diffclock(clock_t clock1,clock_t clock2)
{
double diffticks=clock1-clock2;
double diffms=(diffticks)/(CLOCKS_PER_SEC/1000);
return diffms;
}
int main()
{

int n1,n2,n3,i,choice,a[100],b[100],c[100];

cout<<" enter no of elements of random array:";
cin>>n1;
cout<<" enter elements";
for(i=0;i<n1;i++)
{
cin>>a[i];
}
cout<<" enter no of elements of sorted array:";
cin>>n2;
cout<<" enter elements";
for(i=0;i<n2;i++)
{
cin>>b[i];
}
cout<<" enter no of elements of almost sorted array:";
cin>>n3;
cout<<" enter elements";
for(i=0;i<n3;i++)
{
cin>>c[i];
}
cout<<" enter your choice 1.selection sort 2.insertion sort";
cin>>choice;
switch(choice)
{
case 1:
cout<<" time for random numbers";
selection(a,n1);
cout<<" time for sorted numbers";
selection(b,n2);
cout<<" time for almost sorted numbers";
selection(c,n3);
break;
case 2:
cout<<" time for random numbers";
insertion(a,n1);
cout<<" time for sorted numbers";
insertion(b,n2);
cout<<" time for almost sorted numbers";
insertion(c,n3);
break;
}
}
void selection(int a[],int n)
{
clock_t tic = clock();
int p,k,min,loc,temp;
for(p=1; p<=n-1; p++)
{
min=a[p];
loc=p;

for(k=p+1; k<=n; k++)
{
if(min>a[k])
{
min=a[k];
loc=k;
}
}

temp=a[p];
a[p]=a[loc];
a[loc]=temp;

}
clock_t toc = clock();
cout<<diffclock(tic,toc);
}
void insertion(int a[],int n)
{
clock_t tic = clock();
int p,ptr,temp;
a[0]=0;

for(p=2; p<=n; p++)
{
temp=a[p];
ptr=p-1;

while(temp<a[ptr])
{
a[ptr+1]=a[ptr];
ptr--;
}

a[ptr+1]=temp;
}
clock_t toc = clock();
cout<<cout<<diffclock(tic,toc);
}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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