Assignment 5 Summary Write a program to sort and search an array and record an a
ID: 3621238 • Letter: A
Question
Assignment 5Summary
Write a program to sort and search an array and record an analysis of the operations.
Requirements
A) Using an input file, read a list of exactly 10,000 unique numbers into two identical arrays (int select[], int bubble[]). Included in the input file is a second set of numbers. Read the second set of numbers into a third array, search[]. Below the requirements, you will find a sample input file format.
B) Sort select[] using a selection sort. Using an accumulator, keep track of the number of swaps executed.
C) Sort bubble[] using a bubble sort. Using an accumulator, keep track of the number of swaps executed.
D) For each element in search[], search select[] for the element using a linear search.
a) Using an accumulator, record the number of comparisons made.
b) After all the elements in the third array (search[]) have been located in the select[] array, record the average number of comparisons.
E) For each element in search[], search select[] for the element using a binary search.
a) Using an accumulator, record the number of comparisons made.
b) After all the elements in the third array (search[]) have been located in the select[] array, record the average number of comparisons.
F) Print the results to the console.
a) Print the array before it is sorted.
b) Print the array after it has been sorted.
c) Print the number of swaps made when the selection sort is performed.
d) Print the number of swaps made when the bubble sort is performed.
e) Print the average number of comparisons when searching using the linear search.
f) Print the average number of comparisons when searching using the binary search.
Format of Input File
12 45 134 6 1 8 4561 7391
…
Hints
?? Use lots of functions to perform exactly one task and one task only.
?? Use the algorithms in the book
?? Use your own input file of a considerably small size for development
Explanation / Answer
please rate - thanks
#include <iostream>
#include <fstream>
using namespace std;
int input(int[],int,int[]);
void copy(int[],int[],int);
void selectsort(int[],int,int&);
void bubblesort(int[],int,int&);
void print(int[],int,string);
int linearsearch(int[],int,int);
int binarysearch(int[],int,int);
int main()
{int select[10000],bubble[10000],search[10000],m,i,c;
int bcount=0,scount=0,n=10; //n=10 has to be change to n=10000
m=input(select,n,search);
copy(select,bubble,n);
print(select,n,"Select before sorted ");
print(bubble,n,"bubble before sorted ");
selectsort(select,n,scount);
bubblesort(bubble,n,bcount);
print(select,n,"Select after sorted ");
print(bubble,n,"bubble after sorted ");
cout<<"swaps in selection sort: "<<scount<<endl;
cout<<"swaps in bubble sort: "<<bcount<<endl;
bcount=0;
scount=0;
for(i=0;i<m;i++)
{bcount+=binarysearch(select,n,search[i]);
scount+=linearsearch(select,n,search[i]);
}
cout<<"average comparisons using binarysearch: "<<bcount/(double)m<<endl;
cout<<"average comparisons using linearsearch: "<<scount/(double)m<<endl;
system("pause");
return 0;
}
int linearsearch(int a[],int n,int key)
{int i=0,max=n;
for(i=0;i<max;i++)
if(a[i]==key)
{return i+1;
}
}
int binarysearch(int a[],int n,int key)
{int low=0,max=n,mid,count=0;
while(low<=max )
{mid=(low+max)/2;
count++;
if(a[mid]<key)
low = mid + 1;
else
{count++;
if( a[ mid ]>key )
max = mid - 1;
else
{return count;
}
}
}
}
void print(int a[],int n, string mess)
{int i;
cout<<mess;
for(i=0;i<10;i++)
cout<<a[i]<<" ";
cout<<" ";
}
void selectsort(int a[],int n,int& c)
{ int i,j,min,index,temp,k;
for(i=0;i<n-1; i++)
{index=i;
min=a[i];
for(j=i+1;j<n;j++)
{if(min>a[j])
{index=j;
min=a[j];
}
}
temp=a[i];
a[i]=a[index];
a[index]=temp;
c++;
}
}
void bubblesort(int a[],int n,int& c)
{int i,j,temp;
for (i=0; i<n-1; i++)
for (j=0; j<n-1-i; j++)
if (a[j+1] < a[j])
{temp = a[j];
a[j] = a[j+1];
a[j+1] = temp;;
c++;
}
}
int input(int a[],int n,int b[])
{int i=0;
ifstream in;
char filename[30];
cout<<"what is the name of the file you are using? ";
cin>>filename;
in.open(filename); //open file
if(in.fail()) //is it ok?
{ cout<<"file did not open please check it ";
system("pause");
exit(1);
}
for(i=0;i<n;i++)
in>>a[i];
i=1;
in>>b[0];
while(in)
in>>b[i++];
in.close();
return i-1;
}
void copy(int a[],int b[],int n)
{int i;
for(i=0;i<n;i++)
b[i]=a[i];
}