C++ Programming

Not allowed to use std:: sort

In this assignment, we will keep track of the strings a user has entered and the amount of times each string was recorded.

Create an array of strings of a large size. 1000 is a good number. You will not use the entire array, but you will partially fill it as the program runs. Create a variable that keeps track of the number of different inputs that have been entered, so you know how much of the array you have already filled.

Create a parallel array of ints to store the frequency of each string, which is the same number of elements as the string array.

Create a menu. Use the following code:

 cout << "(1) Enter a string" << endl; cout << "(2) Print a sorted list of inputs and their frequencies" << endl; cout << "(3) Quit" << endl;  

If the user chooses option 1, prompt them to enter a string:

 cout << "Enter a string: ";  

If you used cin to input the menu choice, be sure to use cin.ignore() before calling getline to input the string.

Once the user inputs the string, implement the following logic:

• Search the string array for the input string using binary search
• If the string was not found:
  • Store the new string in the first unused index of the string array
  • Set the frequency to 1 in the first unused index of the frequency array
  • Sort the string array in parallel with the frequency array, such that the strings are sorted alphabetically and the frequency information about each string stays with its corresponding string
    • Use insertion sort
    • The easiest way to perform this dual sort is to sort as if you were only sorting the string array, and whenever you swap elements in the string array, swap the same elements in the frequency array. This way the frequency array mirrors the string array.
  • Don't forget to increment your variable that keeps track of the number of inputs in the array here. Remember you are not using all 1000 elements of the array, so you need this variable updated to know the boundaries.
• If the input string was found in the array:
  • Increment the frequency of that string by 1.

If the user chooses menu option 2, print the sorted list of strings and their frequencies. A sample output is shown below:

 (1) Enter a string (2) Print a sorted list of inputs and their frequencies (3) Quit 1 Enter a string: you know nothing jon snow (1) Enter a string (2) Print a sorted list of inputs and their frequencies (3) Quit 1 Enter a string: chaos is a ladder (1) Enter a string (2) Print a sorted list of inputs and their frequencies (3) Quit 1 Enter a string: you know nothing jon snow (1) Enter a string (2) Print a sorted list of inputs and their frequencies (3) Quit 1 Enter a string: valar morgulis (1) Enter a string (2) Print a sorted list of inputs and their frequencies (3) Quit 1 Enter a string: winter is coming (1) Enter a string (2) Print a sorted list of inputs and their frequencies (3) Quit 1 Enter a string: winter is coming (1) Enter a string (2) Print a sorted list of inputs and their frequencies (3) Quit 1 Enter a string: zebras are cool (1) Enter a string (2) Print a sorted list of inputs and their frequencies (3) Quit 1 Enter a string: winter is coming (1) Enter a string (2) Print a sorted list of inputs and their frequencies (3) Quit 2 Input: chaos is a ladder Frequency: 1 Input: valar morgulis Frequency: 1 Input: winter is coming Frequency: 3 Input: you know nothing jon snow Frequency: 2 Input: zebras are cool Frequency: 1 (1) Enter a string (2) Print a sorted list of inputs and their frequencies (3) Quit 3  

Don't forget that capital letters are sorted alphabetically earlier than lowercase. This doesn't mean your code isn't working.

For searching and sorting your arrays, use the following prototypes. I will be unit testing them:

 void sortInputs(string [], int [], int); ///parameters: string array, frequency array, number of inputs int searchInputs(string [], string, int); ///parameters: string array, search string, number of inputs