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

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.

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.

Here is some code to get you going on this:

void sortInputs(string strings[], int freqs[], int size) { int i = 0; int j = 0; string sTemp = 0; // Temporary variable for swapping string array int iTemp = 0; //Temporary variable for swapping freq array for (i = 1; i < size; ++i) { j = i; // Insert numbers[i] into sorted part // stopping once numbers[i] in correct position while (j > 0 && strings[j] < strings[j - 1]) { // Swap numbers[j] and numbers[j - 1] sTemp = strings[j]; strings[j] = strings[j - 1]; strings[j - 1] = sTemp; ///swap the same indexes in the freqs array --j; } } return; } 

If instead the input string already exists in the array of stored inputs, all you need to do is 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: zombies! (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: zombies! 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