The purpose of this assignment is to familiarize you with sort algorithms. Problem Description is as follows:
8. Search Benchmarks Write a program that has at least 20 250 integers stored in an array in ascending order. It should call a function that uses the linear search algorithm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that uses the binary search algorithm to locate the same value. It should also keep count of the number of comparisons it makes. Display these two counts on the screen. |
bonus_assignment_INCOMPLETE.cpp
In this assignment, a 250 element array is created and populated with random numbers. Lines 27 and 28 place specific values in the array, which will be found since we placed them in the array. The program keeps a count of the number of comparisons made for linear searches and binary searches.
// Chapter 9 - Programming Challenge 8, Search Benchmarks // This program compares the number of comparisons used by linear // search vs. binary search to find a value. #include <iostream> #include <iomanip> using namespace std; // Function prototypes int linearSearchBench(int[], int, int); int binarySearchBench(int[], int, int); void print_array(int *, int); void sort_array(int *arr_param, int size); int main() { const int SIZE = 250; int numCompares; // Accumulator to count the number of comparisons int arr_tests[SIZE] = {}; for (auto &one_num : arr_tests) one_num = rand() % 1001 + 2000; arr_tests[124] = 2496; // Place value in the middle of the array arr_tests[249] = 5000; //Place value at the end of the array sort_array(arr_tests, SIZE); print_array(arr_tests, SIZE); numCompares = linearSearchBench(arr_tests, SIZE, 2496); cout << "Linear Search. Searching for 2496 (middle of array). " << "The linear search made " << numCompares << " comparisons.\n"; numCompares = linearSearchBench(arr_tests, SIZE, 5000); cout << "Linear Search. Searching for 5000 (last element in array). " << " The linear search made " << numCompares << " comparisons.\n"; numCompares = linearSearchBench(arr_tests, SIZE, 8000); cout << "Linear Search. Searching for 8000 (Not in array). " << "The linear search made " << numCompares << " comparisons.\n\n"; numCompares = binarySearchBench(arr_tests, SIZE, 296); cout << "Binary Search. Searching for 2496. " << "The binary search made " << numCompares << " comparisons.\n"; numCompares = binarySearchBench(arr_tests, SIZE, 5000); cout << "Binary Search. Searching for 5000 (last element in array). " << "The binary search made " << numCompares << " comparisons.\n"; numCompares = binarySearchBench(arr_tests, SIZE, 8000); cout << "Binary Search. Searching for 8000 (Not in array). " << "The binary search made " << numCompares << " comparisons.\n"; system("pause"); return 0; } /******************************************************************** * print_array * * Called by: main * * Passed : An array to sprint, the number of elements in * * the array, * * Purpose : To print elements of the array * * Returns : nothing * ********************************************************************/ void print_array(int *arr_param, int size) { } /******************************************************************** * sort_array * * Called by: main * * Passed : An array to sprint, the number of elements in * * the array, * * Purpose : To use a sort algorithm and sort array * * Returns : nothing * ********************************************************************/ void sort_array(int *arr_param, int size) { } /******************************************************************** * linearSearchBench * * Called by: main * * Passed : An array to search in, the number of elements in * * the array, and the value to search for * * Purpose : To count the number of comparisons made to complete * * the linear search * * Returns : The comparison count * ********************************************************************/ int linearSearchBench(int arr_param[], int size, int inp_val) { int comparisons = 0; return comparisons; } /****************************************************************** * binarySearchBench * * Called by: main * * Passed : An array to search in, the number of elements in * * the array, and the value to search for * * Purpose : To count the number of comparisons made to complete * * the binary search * * Returns : The comparison count * ******************************************************************/ int binarySearchBench(int arr_param[], int size, int inp_val) { bool found = false; int comparisons = 0; return comparisons; }
Source Code:
#include<iostream>
#include<iomanip>
#include<stdlib.h>
using namespace std;
// Function prototypes
int linearSearchBench(int[], int, int);
int binarySearchBench(int[], int, int);
void print_array(int *, int);
void sort_array(int *arr_param, int size);
int main()
{
const int SIZE = 250;
int numCompares; // Accumulator to count the number of
comparisons
int arr_tests[SIZE] = {};
for (int i=0;i<SIZE;i++)
arr_tests[i] = rand() % 1001 + 2000;
arr_tests[124] = 2496; // Place value in the middle of the
array
arr_tests[249] = 5000; //Place value at the end of the array
sort_array(arr_tests, SIZE);
print_array(arr_tests, SIZE);
numCompares = linearSearchBench(arr_tests, SIZE, 2496);
cout << "Linear Search. Searching for 2496 (middle of array).
"
<< "The linear search made " << numCompares
<< " comparisons.\n";
numCompares = linearSearchBench(arr_tests, SIZE, 5000);
cout << "Linear Search. Searching for 5000 (last element in
array). "
<< " The linear search made " << numCompares
<< " comparisons.\n";
numCompares = linearSearchBench(arr_tests, SIZE, 8000);
cout << "Linear Search. Searching for 8000 (Not in array).
"
<< "The linear search made " << numCompares
<< " comparisons.\n\n";
numCompares = binarySearchBench(arr_tests, SIZE, 296);
cout << "Binary Search. Searching for 2496. "
<< "The binary search made " << numCompares
<< " comparisons.\n";
numCompares = binarySearchBench(arr_tests, SIZE, 5000);
cout << "Binary Search. Searching for 5000 (last element in
array). "
<< "The binary search made " << numCompares
<< " comparisons.\n";
numCompares = binarySearchBench(arr_tests, SIZE, 8000);
cout << "Binary Search. Searching for 8000 (Not in array).
"
<< "The binary search made " << numCompares
<< " comparisons.\n";
system("pause");
return 0;
}
/********************************************************************
* print_array *
* Called by: main *
* Passed : An array to sprint, the number of elements in *
* the array, *
* Purpose : To print elements of the array *
* Returns : nothing *
********************************************************************/
void print_array(int *arr_param, int size)
{
for(int i=0;i<size;i++){
cout<<arr_param[i]<<"
";
}
cout<<endl;
}
/********************************************************************
* sort_array *
* Called by: main *
* Passed : An array to sprint, the number of elements in *
* the array, *
* Purpose : To use a sort algorithm and sort array *
* Returns : nothing *
********************************************************************/
void sort_array(int *arr_param, int size)
{
//Using Bubble Sort to sort the array
for(int i=0;i<size;i++){
for(int j=0;j<size-i;j++){
if(arr_param[j]<arr_param[j-1]){
int temp = arr_param[j];
arr_param[j] = arr_param[j-1];
arr_param[j-1] = temp;
}
}
}
}
/********************************************************************
* linearSearchBench *
* Called by: main *
* Passed : An array to search in, the number of elements in *
* the array, and the value to search for *
* Purpose : To count the number of comparisons made to complete
*
* the linear search *
* Returns : The comparison count *
********************************************************************/
int linearSearchBench(int arr_param[], int size, int inp_val)
{
int comparisons = 0;
//Loop over the array for
finding the element
for(int i=0;i<size;i++){
comparisons++;
if(arr_param[i]==inp_val){
break;
}
}
return comparisons;
}
/******************************************************************
* binarySearchBench *
* Called by: main *
* Passed : An array to search in, the number of elements in *
* the array, and the value to search for *
* Purpose : To count the number of comparisons made to complete
*
* the binary search *
* Returns : The comparison count *
******************************************************************/
int binarySearchBench(int arr_param[], int size, int inp_val)
{
bool found = false;
int comparisons = 0;
int l = 0;
int r = size - 1;
int m = size/2;
while(!found){
if(m==l
&& arr_param[m]!=inp_val){
comparisons+=2;
break;
}
comparisons++;
if(arr_param[m]==inp_val){
found = true;
continue;
}
comparisons++;
if(arr_param[m]<inp_val){
l = m+1;
m = (r-l+1)/2;
continue;
}
comparisons++;
if(arr_param[m]>inp_val){
r = m-1;
m = (r-l+1)/2;
continue;
}
}
return comparisons;
}
Output:
Please appreciate the solution if you find it helpful.
If you have any doubts in the solution feel free to ask me in the comment section.
The purpose of this assignment is to familiarize you with sort algorithms. Problem Description is as follows: 8. Search Benchmarks Write a program that has at least 20 250 integers stored in an ar...
The purpose of this assignment is to familiarize you with sort algorithms. Problem Description is as follows: 8. Search Benchmarks Write a program that has at least 20 250 integers stored in an array in ascending order. It should call a function that uses the linear search algorithm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that...
Java: Write an application that has an array of at least 20 integers. It should call a method that uses the sequential search algorithm to locate one of the values. The method should keep a count of the number of comparisons it makes until it finds the value. Then the program should call another method that uses the binary search algorithm to locate the same value. It should also keep count of the number of comparisons it makes. Display these...
Benchmark Searching and Sorting Write a program that has an array of at least 20 strings that you will have your user enter. It should call a function that uses the linear search algorithm to locate one of the values. The function should keep a count of the number of comparisons it makes until it finds the value. The program then should call a function that uses the binary search algorithm to locate the same value. It should also keep...
My following program has an array which holds 1000 random integers between 1-1000. Now I need help to create an array that holds 10,000 random integer between 1-1000 in my following program. The main goal of this program is time analysis by using bubble sort and binary search algorithms. Please do the following task; 1. Replace the 1000 random integers with 10,000 random integers After change please answer the following question 2. what will be happen, if an array holds...
C programming (you don't need to write program) Problem 1 [Linear Search with Early Stop] Below you will find a linear search function with early stop. A linear search is just a naive search - you go through each of the elements of a list one by one. Early stop works only on sorted list. Early stop means, instead of going through whole list, we will stop when your number to search can no longer be possibly found in the...
SortAndSearch.cpp – Objectives: Binary Search and Selection sort You are given a list of 20 names as follows: {"Collins, Bill", "Smith, Bart", "Michalski, Joe", "Griffin, Jim", "Sanchez, Manny", "Rubin, Sarah", "Taylor, Tyrone", "Johnson, Jill", "Allison, Jeff", "Moreno, Juan", "Wolfe, Bill", "Whitman, Jean", "Moretti, Bella", "Wu, Hong", "Patel, Renee", "Harrison, Rose", "Smith, Cathy", "Conroy, Pat", "Kelly, Sean", "Holland, Beth"}; Write a program to sort and display the names in alphabet order (use selection sort). The program prompts...
In C language Write a program that includes a function search() that finds the index of the first element of an input array that contains the value specified. n is the size of the array. If no element of the array contains the value, then the function should return -1. The program takes an int array, the number of elements in the array, and the value that it searches for. The main function takes input, calls the search()function, and displays...
Language = c++ Write a program to find the number of comparisons using the binary search and sequential search algorithms as follows: o Suppose list is an array of 1000 elements. o Use a random number generator to fill the list. o Use the function insertOrd to initially insert all the elements in the list. o You may use the following function to fill the list: void fill(orderedArrayListType& list) { int seed = 47; int multiplier = 2743; ...
How can i make a counter for the number of exchanges made in the linear algorithm?? The binary counter works but the linear doesn't. Here's my code. #include <iostream> using namespace std; void selectionSort(int[], int, int& ); void showSelection(int[], int); void sortArray(int[], int, int&); void showArray(const int[], int); int main() { int values[25] = { 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24...
C++ Time the sequential search and the binary search methods several times each for randomly generated values, then record the results in a table. Do not time individual searches, but groups of them. For example, time 100 searches together or 1,000 searches together. Compare the running times of these two search methods that are obtained during the experiment. Regarding the efficiency of both search methods, what conclusion can be reached from this experiment? Both the table and your conclusions should...