Write, compile, and run a C++ program that generates 200 random integers in betw
ID: 3572022 • Letter: W
Question
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 Bubble 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. Also, please implement your Bubble sort algorithm, Binary Search and Sequential Search algorithms as three separate functions that will be called from the function main().
Explanation / Answer
#include <iostream>
#include <fstream>
using namespace std;
void BubbleSort(int *arr,int numC){ // Function to perform bubble sort
int temp=0;
for(int i=0;i<numC;i++){
for(int j=i+1;j<numC;j++){
if(arr[i] > arr[j]){ //If first value is greater than second then
temp = arr[i]; //Swapping values
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
int SequentialSearch(int *arr,int len, int n){ //Function to perform sequential search
for(int i=0;i<len;i++){
if(arr[i] == n) return i; // if the value is found then return its related index
}
return -1;
}
int BinarySearch(int *arr, int len, int n){ //Function to search a number using binary search
int start=0,end=len,mid;
while(start < end){ //Perform the checking until start is lesser than end
mid = (start+end)/2; //Calculate mid value
if(arr[mid] == n) { //If value in the middle of array is the number that we searching for then
return mid; //return mid index
}
else if(arr[mid] > n){ //If value in the middle is greater than the number that we searching for then
end = mid; //change the value of end to mid
}
else if(arr[mid] < n){ //If value in the middle is lesser than the number that we searching for then
start = mid + 1; //change the value of start to mid+1
}
}
if(arr[start] == n){ //This condition is to check when start equal to end and the value in that index is n then
return start; // return the index
}
return -1; //If the number is not found in the array then return -1
}
int main()
{
// open a file in write mode.
ofstream outfile;
outfile.open("numbers.txt");
int numC = 200,n=0;
int arr[200];
for(int i=0;i<numC;i++){ //Loop to generate 200 random numbers
arr[i] = rand()%numC+1; //storing the randomly generated numbers in array
}
BubbleSort(arr,numC); //Calling bubble sort function
for(int i=0;i<numC;i++){ //Loop to write all numbers in output file
outfile << arr[i] << ","; // writing random numbers in output file
}
cout << "Enter number to search : ";
cin >> n; //Taking the search input number from user
int SSindex = SequentialSearch(arr,numC,n); //Calling the sequentialSearch function and assigning its value to a variable
int BSindex = BinarySearch(arr,numC,n); //Calling the BinarySearch function and assigning its value to a variable
outfile << endl << SSindex << " " << BSindex; //Writing both the values in the same output file in a new line
return 0;
}
//Sample output
//Enter number to search : 30
//2,3,4,8,9,12,12,12,13,14,15,19,19,20,20,20,22,22,23,25,27,27,28,28,29,29,29,30,30,30,30,32,33,35,35,35,36,38,38,41,42,42,43,44,45,46,47,47,50,52,52,53,57,57,57,58,59,59,60,60,61,63,63,66,68,68,70,71,72,74,75,76,76,77,77,81,82,82,84,85,87,87,88,89,90,91,92,92,93,93,95,96,98,98,98,101,102,103,104,106,106,107,109,110,114,115,116,116,116,118,118,120,122,122,124,124,125,125,125,126,127,127,128,128,129,129,130,130,130,130,131,133,133,136,136,137,137,137,138,140,140,141,141,144,144,146,150,151,151,152,154,155,156,157,157,163,164,165,165,165,166,166,168,168,168,168,169,169,169,171,171,171,172,173,174,178,179,179,180,181,183,183,184,185,185,187,187,187,188,189,194,194,194,194,196,196,197,197,199,200,
//27 29
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.