In C++ Using the vector type as your list, implement functions for each of seque
ID: 3689601 • Letter: I
Question
In C++
Using the vector type as your list, implement functions for each of sequential search, binary search, bubble sort, and insertion sort. You may use function templates, or just force a particular vector type (for example vector).
Create a test program where you add several items to a vector. Use your sequential search function several times to get the index of items, and show when an item is not found. Then use your bubble sort function to sort the vector, and then print out the entire vector to show it is sorted. Now use your binary search function several times to get the index of items, and show when an item is not found. Now add a few more items to the vector, and use insertion sort to sort that, and then print the whole vector to show it is sorted. Alternatively, you could implement a looping test menu that gives options, such as add item, print whole list, use insertion sort, use binary search, etc.
grading rubric:
(10 points) Sequential Search function
• (10 points) Binary Search function
• (10 points) Bubble sort function
• (10 points) Insertion sort function
• (10 points) Vector usage
Explanation / Answer
#include <iostream> // inclusion of iostream vector
#include<vector>
#include <algorithm> // std::binary_search, std::sort
using namespace std;
int s_search(int s); // function declarations
void bubblesort();
void b_search();
void insertionsort();
int arr[]={3,5,4,2,7,8}; // array values to construct vector
vector<int> v(arr,arr+sizeof(arr)/sizeof(arr[0])); // vector initialization
int main() { // main function starts here
int c=0,value; // integers for operations
cout<<"Welcome ";
cout<<"Enter 1 to sequential search: "; // menu option for the user to select an option ex: if u enter 1 sequential search will be performed
cout<<"Enter 2 for bubblesort : ";
cout<<"Enter 3 for binary_search: ";
cout<<"enter 4 to add values to vector and insertionsort it ";
cout<<"Enter 5 to exit ";
cin>>c; // reading input number from the user
while(c!=5) // continuing with the menu until user enters 5
{
cout<<"Enter 1 to sequential search: ";
cout<<"Enter 2 for bubblesort : ";
cout<<"Enter 3 for binary_search: ";
cout<<"enter 4 to add values to vector and insertionsort it";
cout<<"Enter 5 to exit";
cin>>c;
switch(c) // switch to select users option
{
case 1: cout<<"Enter a value to search:";
cin>>value;
s_search(value); break;
case 2:bubblesort(); break;
case 3: b_search(); break;
case 4: cout<<"Enter an element to add: ";
cin>>value;
v.push_back(value);
insertionsort();
break;
case 5:cout<<"Thank you"; break;
ddefault: "Done"; break;
}
}
return 0;
}
int s_search(int n) // searching a value sequential search
{
for (int i = 0; i < v.size(); i++){
if (v[i] == n)
return i;
}
return -1;
}
void bubblesort() // bubble sort function
{
bool swapp = true;
while(swapp){
swapp = false;
for (int i = 0; i < v.size(); i++) {
if (v[i]>v[i+1] ){
v[i] += v[i+1];
v[i+1] = v[i] - v[i+1];
v[i] -=v[i+1]; // swapping on the comparisiion
swapp = true;
}
}
}
for (int i=0; i <v.size(); i++) {
cout<<v[i]<<" "; // printing after sorting
}
cout<<endl;
}
bool myfunction (int i,int j) { return (i<j); } // temperaroy function to compare
void b_search() // binary search function
{
// using default comparison:
std::sort (v.begin(), v.end());
std::cout << "looking for a 3... ";
if (std::binary_search (v.begin(), v.end(), 3))
std::cout << "found! "; else std::cout << "not found. ";
// using myfunction as comp:
std::sort (v.begin(), v.end(), myfunction);
std::cout << "looking for a 6... ";
if (std::binary_search (v.begin(), v.end(), 6, myfunction))
std::cout << "found! "; else std::cout << "not found. ";
}
void insertionsort() // function- insertion sort
{
int i, j, tmp;
for (i = 1; i < v.size(); i++) {
j = i;
while (j > 0 && v[j - 1] > v[j]) {
tmp = v[j];
v[j] = v[j - 1];
v[j - 1] = tmp;
j--;
}
}
for(int k=0;k<v.size();k++)
cout<<v[i];
}