Concepts tested by the program: 1. Work with random numbers and random number ge

Question

Concepts tested by the program: 1. Work with random numbers and random number generation 2. Work with arrays 3. Use file operations 4. To learn and use Bubble 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 7. Implement functions besides function main() 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 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(). Output: Your output should be in the format shown below:

Explanation / Answer

Assumption : since this question does not contain the output format , i am only storing the results in a file. One can simple use "cout"<<" in place of "myfile<<" to output the results in this code.

** Binary search Algorithm :

Given an array A of n elements with values or records A0 ... An1, sorted such that A0 ... An1, and target value T, the following subroutine uses binary search to find the index of T in A.[6]

**Bubble Sort Algorithm :

**Solution to this question

#include <iostream>
#include <fstream>
#include <stdlib.h>

using namespace std;

void bubbleSort(int array[])
{
   int i , j;
   for(i=0;i<200;i++)
   {
       for(j=i+1;j<200;j++)
       {
           if(array[i]<array[j])
           {

/*sorting 2 numbers*/

int temp = array[i];

array[i]=array[j];
               array[j]=temp;
           }
       }
   }
  
}

int binarySearch(int array[], int search )
{
   int first,last;
   int middle = 199/2;
   while(first<=last)
   {
       if (array[middle] < search)
    first = middle + 1;
  
   else if (array[middle] == search)
   {
   return middle;
}
else
last = middle - 1;

middle = (first + last)/2;
}
  
   /*if integar not found we return 0*/
return 0;
}

int seqSearch(int array[], int search)
{
   int i;
   for(i=0;i<200;i++)
   {
       if(search == array[i])
       {
           return i;
       }
   }
   /*if integar not found we return 0*/
return 0;
}

int main() {
   int i,j,k;
   int array[205];
  
   /* PART 1 : storing 200 numbers randomly */
   for(i=0;i<200;i++)
       array[i]=rand()%200;
      
   /* PART 2 : sorting them with bubble sort */
   bubbleSort(array);
  
   /*PART 3 : writing output to a file */
   ofstream myfile;
   myfile open("output.txt");
   for(i=0;i<200;i++)
   {
       myfile<<"element number"<<i<<"is"<<array[i]<<" ";
   }
  
  
   /*PART 4 : user input */
   int index;
   cin>>"enter index to search">>index;
  
   /*PART 5 : finding result with binary search */
   int result1 = binarySearch(array,index);

   if(result1 != 0)
       myfile <<"Your int is found at location "<<result1;
   else
       myfile <<"Your integar is not found!! ";
      

   /*PART 6: finding result with sequential search*/
   int result2 = seqSearch(array,index);
   if(result2 != 0)
       myfile <<"Your int is found at location "<<result2;
   else
       myfile <<"Your integar is not found! ";
   myfile.close();
   return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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