Project 7 consists of a C++ Program: Concepts tested by the program: Work with r
ID: 3771730 • Letter: P
Question
Project 7 consists of a C++ Program:
Concepts tested by the program:
Work with random numbers and random number generation
Work with arrays
Use file operations
4. To learn and use Selection sort to sort an array
5. To learn and use binary search to a sorted array
6. To learn and use sequential search to an array
Program: Write, compile, and run a C++ program that generates 200 random integers in between 1 to 200. Some of the randomly generated integers may be repeated as well. Next sort the randomly generated 200 integers using the Selection sort algorithm. Store the sorted numbers in an output data file. Then prompt the user to enter an integer in between 1 to 200 (inclusive) out of the keyboard as a key element. Next find out the location of the key element in the sorted array using both the binary search and the sequential search algorithms. The result returned by binary search and the sequential search algorithm may vary for repeated elements inside the sorted array. This is acceptable. Please write out the results returned by the binary search and the sequential search algorithms to the output data file.
Explanation / Answer
#include<iostream>
#include <stdio.h> /* printf, NULL */
#include <stdlib.h> /* srand, rand */
#include <time.h> /* time */
#include <fstream>
using namespace std;
void selection_sort (int ar[], int size)
{
int min_ele_loc;
for (int i = 0; i < size; ++i)
{
//Find minimum element in the unsorted array
//Assume it's the first element
min_ele_loc = i;
//Loop through the array to find it
for (int j = i + 1; j < size; ++j)
if (ar[j] < ar[min_ele_loc])
//Found new minimum position, if present
min_ele_loc = j;
//Swap the values
int temp = ar[i];
ar[i] = ar[min_ele_loc];
ar[min_ele_loc] = temp;
}
}
int binary_search(int array[],int first,int last, int search_key)
{
int index;
if (first > last)
index = -1;
else
{
int mid = (first + last)/2;
if (search_key == array[mid])
index = mid;
else
if (search_key < array[mid])
index = binary_search(array,first, mid-1, search_key);
else
index = binary_search(array, mid+1, last, search_key);
} // end if
return index;
}// end binarySearch
int linear_search(int a[],int size,int search_key){
int i;
for(i=0;i<size;i++)
if(a[i] == search_key)
return i;
return -1;
}
int main(){
ofstream myfile;
int A[200],i,n;
srand (time(NULL));
for(i=0;i<200;i++){
A[i] = rand()%200;
printf("%d ",A[i]);
}
printf(" ");
selection_sort(A,200);
myfile.open ("output.txt");
// myfile << "Writing this to a file. ";
for(i=0;i<200;i++){
// A[i] = rand()%200;
printf("%d ",A[i]);
myfile << A[i]<<" ";
}
// myfile.open ("output.txt");
// myfile << "Writing this to a file. ";
//myfile.close();
cout<<"Enter an integer in between 1 to 200 (inclusive):";
cin>>n;
int index = binary_search(A,0,200,n);
if(index == -1){
cout<<"element not found";
myfile << "Element not found in Binary Search";
}
else {
cout<< "binary search results for "<<n<<" is in the index : "<<index<<endl;
myfile<< " binary search results for "<<n<<" is in the index : "<<index<<endl;
}
index = linear_search(A,200,n);
if(index == -1){
cout<<"element not found";
myfile << "Element not found in linear Search";
}
else{
cout<< "linear search results for "<<n<<" is in the index : "<<index<<endl;
myfile<< " linear search results for "<<n<<" is in the index : "<<index<<endl;
}
myfile.close();
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.