Please in C++. Using the vector type as your list, implement functions for each
ID: 3686625 • Letter: P
Question
Please 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 <int>).
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 user 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.
Explanation / Answer
#include<iostream>
#include<vector>
using namespace std;
//insertion sort
void insertionSort (vector<int>& data)
{
size_t i, j;
int tmp;
for (i=1; i<data.size(); i++)
{
j=i;
tmp=data[i];
while (j>0 && tmp<data[j-1])
{
data[j]=data[j-1];
j--;
}
data[j]=tmp;
}
}
/*Selection sort will sort the vectors in ascending order*/
void selSort(vector<int>& v)
{
int temp, min;
for( size_t i = 0; i < v.size(); i++){
min = i;
for (size_t j = 1; j < v.size(); j++){
if (v[j] < v[min])
min = j;
}
temp = v[i];
v[i] = v[min];
v[min] = temp;
}
}//end selection sort
// Bubble sort
void bubbleSort(vector<int>& a)
{
bool swapp = true;
while(swapp){
swapp = false;
for (size_t i = 0; i < a.size()-1; i++) {
if (a[i]>a[i+1] ){
a[i] += a[i+1];
a[i+1] = a[i] - a[i+1];
a[i] -=a[i+1];
swapp = true;
}
}
}
}
//sequential search
int sequential_search(vector<int> v, int a){
for (size_t i = 0; i < v.size(); i++){
if (v[i] == a)
return i;
}
return -1;
}
// binary search
bool binary_search(const vector<int>& sorted_vec, int key) {
size_t mid, left = 0 ;
size_t right = sorted_vec.size(); // one position passed the right end
while (left < right) {
mid = left + (right - left)/2;
if (key > sorted_vec[mid]){
left = mid+1;
}
else if (key < sorted_vec[mid]){
right = mid;
}
else {
return true;
}
}
return false;
}
//function to print vector
void printVector(vector<int> a){
for (size_t i=0; i <a.size(); i++) {
cout<<a[i]<<" ";
}
cout<<endl;
}
int main(){
vector<int> data;
data.push_back(12);
data.push_back(7);
data.push_back(22);
data.push_back(2);
data.push_back(13);
data.push_back(1);
data.push_back(5);
data.push_back(4);
data.push_back(9);
data.push_back(12);
printVector(data);
//sorting using bubble sort
bubbleSort(data);
//print sorted data
printVector(data);
// binary search
bool isAvailable = binary_search(data, 7);
string status = isAvailable ? "true" : "false";
cout<<"12 is available: "<<status<<endl;
// like that you can test all methods
return 0;
}
/*
Sample run:
12 7 22 2 13 1 5 4 9 12
1 2 4 5 7 9 12 12 13 22
12 is available: true
*/