Write, compile, and run a C++ program that generates 200 random integers in betw

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 Selection sort algorithm. 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 <time.h>
#include <stdlib.h>
#include <fstream>

using namespace std;

void selectSort(int arr[], int n)
{
//pos_min is short for position of min
int pos_min,temp;

for (int i=0; i < n-1; i++)
{
pos_min = i;//set pos_min to the current index of array
  
for (int j=i+1; j < n; j++)
{

if (arr[j] < arr[pos_min])
pos_min=j;
//pos_min will keep track of the index that min is in, this is needed when a swap happens
}
  
//if pos_min no longer equals i than a smaller value must have been found, so a swap must occur
if (pos_min != i)
{
temp = arr[i];
arr[i] = arr[pos_min];
arr[pos_min] = 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 sequential_search(int array[], int size, int search_key)
{
int i;
for(i=0;i<size;i++)
if(array[i] == search_key)
return i;

return -1;
}

int main()
{
srand(time(NULL));
int data[200];
int i,key = 100,index_binary,index_seq;

for(i=0;i<200;i++)
data[i] = rand()%200 +1;

selectSort(data,200);

//cout<<"Enter a elemen to be searched ";
//cin>>key;

index_binary = binary_search(data,0,199,key);
index_seq = sequential_search(data,200,key);

ofstream outfile;
outfile.open("Output.txt");
cout<<"Results written in Output.txt file ";

if(index_binary == -1)
outfile<<key<<" is not present in the array ";
else
{
outfile<<key<<" is present in the array ";
outfile<<"Using binary search "<<key<<" is present at index "<<index_binary<<endl;
outfile<<"Using sequential search "<<key<<" is present at index "<<index_seq<<endl;
}

outfile.close();
}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

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