Binary Search Algorithm & Selection Sort • Using C++ write a program that search
ID: 3712058 • Letter: B
Question
Binary Search Algorithm & Selection Sort
• Using C++ write a program that searches for a string in a vector of strings.
• Use vector of strings (vector<string>) to store a list of unsorted strings. Each of
the elements of this vector can hold more than one word.
• To use binary search algorithms, the vector of strings should be first sorted alphabetically.
• Write a function that sorts the strings in ascending (or descending) order by using a
Selection Sort algorithm.
• Write a function that searches for an string in a vector of sorted strings by using a
binary search algorithm.
• write a program to test your function.
• Additional requirements and instructions:
– No use of global variables.
– Code is well commented.
– Comments for functions describe what they do. They also describe the post
conditions. If parameter names are not descriptive in function headers, the
comments for a function describe the pre conditions as well.
Explanation / Answer
#include <iostream>
#include <cstdlib>
#include <sstream>
#include <string>
#include <fstream>
#include <iomanip>
#include <vector>
using namespace std;
// display the elements of the word vector
void display(vector <string> &words){
vector<string>::iterator it;
for(it = words.begin(); it != words.end(); it++ ) {
cout<< *it << endl; // prints elements.
}
}
//sort the vector using selectionSort
void selectionSort(vector <string> &words)
{
int i, j, min_idx;
int n = words.size();
// One by one move boundary of unsorted subarray
for (i = 0; i < n-1; i++)
{
// Find the minimum element in unsorted array
min_idx = i;
for (j = i+1; j < n; j++)
if (words[j] < words[min_idx])
min_idx = j;
// Swap the found minimum element with the first element
swap(words[min_idx], words[i]);
}
}
// A recursive binary search function. It returns
// location of x in given vecor words[l..r] is present,
// otherwise -1
int binarySearch(vector <string> &words, int l, int r, string x)
{
if (r >= l)
{
int mid = l + (r - l)/2;
// If the element is present at the middle
// itself
if (words[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (words[mid] > x)
return binarySearch(words, l, mid-1, x);
// Else the element can only be present
// in right subarray
return binarySearch(words, mid+1, r, x);
}
// We reach here when element is not
// present in array
return -1;
}
int main(){
vector <string> words ={ "king", "queen", "jack", "jestet", "minister" , "soldier"};
cout << "Initial words are:" << endl;
display(words);
selectionSort(words);
cout << endl << "New order of words are:" << endl;
display(words);
int index = binarySearch(words, 0, words.size() - 1, "minister");
if (index == -1) {
cout << "The word is not found" <<endl;
}
else{
cout << endl << "the string is found at Index :" << index << endl;
}
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.