I am writing a program for class that requires me to do the following. Load a file of words into a vector of strings, allow user to enter a word to search, perform a sequential search, sort the words using Selection Sort, and finally perform a Binary Search.
I managed to get the entire program working as intended except for the Binary Search. For some reason I cannot understand, my Sequential Search function displays all the information correctly while the Binary Search function only displays the initial cout.
Thank you for all the help!
Here is a copy of the current output running my program:
Enter the word to search for: YELL YELL was found successfully after 407 comparisons! Perform selection sort... Perform a binary search using selection sorted vector... Press any key to continue . . .
The code for my program (I know no one likes the use of using namespace std but I am required to do so for my class):
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <fstream>
using namespace std;
void loadWords(vector<string>& words); // load unsorted words from file to vector of strings.
int sequentialSearch(vector<string>& words, string targetWord, int& count); // Perform sequential search and keep track of how many comparisons have happened.
void selectionSort(vector<string>& wordsSorted); // Perform the selection sort on the words.
int binarySearch(vector<string>& wordsSorted, string targetWord, int& count); // Perform binary search and keep track of how many comparisons have happened.
int main()
{
vector<string> words;
vector<string> wordsSorted;
loadWords(words);
wordsSorted = words;
string targetWord;
int count = 0;
cout << "Enter the word to search for: " << endl;
getline(cin, targetWord);
sequentialSearch(words, targetWord, count);
selectionSort(wordsSorted);
binarySearch(words, targetWord, count);
return 0;
}
void loadWords(vector<string>& words)
{
ifstream inFile("unsortedBog.dat");
string word;
while (inFile >> word)
{
words.push_back(word);
}
inFile.close();
}
int sequentialSearch(vector<string>& words, string targetWord, int& count)
{
for (int i = 0; i < words.size(); i++)
{
count++;
if (words[i] == targetWord)
{
cout << targetWord << " was found successfully " << "after " << count << " comparisons!" << endl;
return i;
}
}
cout << "After performing " << count << " comparisons, " << targetWord << " could not be found." << endl;
}
void selectionSort(vector<string>& wordsSorted)
{
cout << "Perform selection sort... \n" << endl;
int min = 0;
string min1;
for (int i = 0; i < wordsSorted.size() - 1; i++)
{
if (wordsSorted[i] < wordsSorted[min])
{
min = i;
}
min1 = wordsSorted[i];
wordsSorted[i] = wordsSorted[min];
wordsSorted[min] = min1;
}
}
int binarySearch(vector<string>& wordsSorted, string targetWord, int& count)
{
cout << "Perform a binary search using selection sorted vector... \n" << endl;
int first = 0,
last = wordsSorted.size() - 1,
mid,
position = -1;
bool found = false;
while (!found && first <= last)
{
int i = 0;
count = i++;
mid = (first + last) / 2;
if (wordsSorted[mid] == targetWord) // If value is found at mid
{
found = true;
position = mid;
cout << "The target word was located successfully after performing " << count << " comparisons.";
return position;
}
else if (wordsSorted[mid] > targetWord) // Lower half
last = mid - 1;
else if (wordsSorted[mid] < targetWord) // Upper half
first = mid + 1;
else
cout << "After performing " << count << " comparisons, the target word could not be found.";
}
}
Aucun commentaire:
Enregistrer un commentaire