In C++ void selectionSort(vector<int> &arr) { for(int i = 0; i < arr.size()-1; i
ID: 3729458 • Letter: I
Question
In C++
void selectionSort(vector<int> &arr)
{
for(int i = 0; i < arr.size()-1; i++) {
for(int j = i + 1; j < arr.size(); j++) {
if(arr[i] > arr[j]) {
swap(arr[i], arr[j]);
}
}
}
}
int binarySearch(vector<int> arr, int from, int to, int value)
{
if (from > to)
return -1;
int mid = (from + to) / 2;
if (arr[mid] == value)
return mid;
else if (arr[mid] < value)
return binarySearch(arr, mid + 1, to, value);
else
return binarySearch(arr, mid - 1, to, value);
}
Implement this algorithm in C++ and test its correctness. Write a main() function to
a. input a set of numbers from an input file into a vector,
b. call and pass the vector to selection sort, and
c.display the sorted numbers.
Use the following input file
D. to prompt the user for a number to search (until ^D) and display the position of the number in the sorted vector. Try your program for the following user input
The output should be:
55050 215-342mExplanation / Answer
#include <iostream>
#include <fstream>
#include <string>
#include <vector>
using namespace std;
void selectionSort(vector<int> &arr)
{
for(int i = 0; i < arr.size()-1; i++) {
for(int j = i + 1; j < arr.size(); j++) {
if(arr[i] > arr[j]) {
swap(arr[i], arr[j]);
}
}
}
}
int binarySearch(vector<int> arr, int from, int to, int value)
{
if (from > to)
return -1;
else if(from == to) {
if(arr[from] == value)
return from;
else
return -1;
}
int mid = (from + to) / 2;
if (arr[mid] == value)
return mid;
else if (arr[mid] < value)
return binarySearch(arr, mid + 1, to, value);
else
return binarySearch(arr, to, mid - 1, value);
}
int main() {
cout << "Enter file name: ";
string filename;
cin >> filename;
ifstream in(filename.c_str());
if(in.is_open()) {
vector<int> vec;
int num;
while(in >> num) {
vec.push_back(num);
}
selectionSort(vec);
// display
for(int i = 0; i < vec.size(); ++i) {
cout << vec[i] << " ";
}
cout << endl;
while(cin >> num) {
cout << binarySearch(vec, 0, vec.size()-1, num) << endl;
}
in.close();
}
return 0;
}