lundi 27 juin 2016

Why won't my function return the correct outputs?

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