CS 12: Programming Assignment 2

Due Date: Wednesday, Oct. 18

Directory To Submit: as2

Create a number of "utility" template functions for dealing with arrays.

The Functions

Following is a list of each function with a description of what it should do. Note that in the descriptions, types are not specified for all of the parameters and return values. In these cases, use the template formal type parameter (see page 206 in the text) as the type.
addValueToArray
This function should take three parameters, the array to add a value to, the value to add, and an integer representing the index of where to add the value. The value should be added to the array at the specified index. This function does not return a value.
sortArrayValues
This function should take two parameters, the array to sort and an integer representing the size of the array. Use a bubblesort algorithm. Figure 5.15 on page 321 shows an example of this, though it assumes the array will be of type integer. You will need to modify the bubbleSort and swap functions shown to make them template functions. This function does not return a value.
findMinMaxValuesInSortedArray
This function should take four parameters, the array to search, an integer representing the size of the array, a reference parameter to hold the minimum value in the array, and a reference parameter to hold the maximum value in the array. The minimum and maximum values from the array should be put into the respective reference parameters, unless the size of the array is 0 (or less), in which case the function should do nothing. Note that since the array is (assumed) sorted, you do not need to search it. This function does not return a value.
printArrayValues
This function should take two parameters, the array and an integer representing the size of the array. It should simply print each element of the array, separated by a space. Also, after every 10'th element, a return character should be printed. This function does not return a value.
findValueInSortedArray
This function should take four parameters, the array to search, the value to search for, an integer representing the lower index to search from, and an integer representing the larger index to search from. The array should be searched for the value, using the algorithm described below, and if found, the value should be returned. If the value is not found, 0 should be returned. Because this is a template function, you will need to typecast 0 to the appropriate type.

Because the array is (assumed) sorted, you should not just search from the beginning to the end of the array for the value. Instead, use a recursive algorithm known as a binary search. Here is the algorithm:

  1. If the lower index is greater than the larger index, return 0 (the value was not found).
  2. Find the midpoint of the array; use the formula (lower index + larger index) / 2.
  3. If the value at the midpoint is the value being searched for, return it (the value was found).
  4. If the value being searched for is less than the value at the midpoint, call findValueInSortedArray, passing the lower index and the midpoint -1 for the lower index and larger index parameters, respectively.
  5. If the value being searched for is greater than the value at the midpoint, call findValueInSortedArray, passing the midpoint + 1 and the larger index for the lower index and larger index parameters, respectively.
main
Your main program should create 2 arrays, one of type integer and one of type character. Each should be of size 20. (Declare a constant for the size and use this constant in your program. Do not use 20 except when declaring the constant.)

After creating the arrays, fill them using the following code:

    for (int i = 0; i < ARRAY_SIZE; ++i )
    {
        addValueToArray( intArray, 64 + ARRAY_SIZE - i, i );
        addValueToArray( charArray, char(64 + ARRAY_SIZE - i), i );
    }
Note that in the preceding code, I assumed the integer array is named intArray, the character array is named charArray, and that the size constant is named ARRAY_SIZE. If you name your arrays and/or constant differently, you will need to modify the code accordingly. The code simply populates each array with values in reverse order.

Once the arrays have been filled, sort them by calling sortArrayValues.

Finally, provide the user a menu of options to choose from:

Allow the user to keep choosing options until "Quit" is selected. For each of the other options, call the appropriate method and print the results.

Sample Run

Following is a sample run of the program:

This program will test some array utility functions.

Please choose from the following options:

A) Print the values in the integer array.
B) Print the values in the character array.

C) Print the minimum/maximum values in the integer array.
D) Print the minimum/maximum values in the character array.

E) Search for a value in the integer array.
F) Search for a value in the character array.

Q) Quit.

Choice: B

The values in the character array are:

A B C D E F G H I J
K L M N O P Q R S T

Please choose from the following options:

A) Print the values in the integer array.
B) Print the values in the character array.

C) Print the minimum/maximum values in the integer array.
D) Print the minimum/maximum values in the character array.

E) Search for a value in the integer array.
F) Search for a value in the character array.

Q) Quit.

Choice: C

The minimum value in the integer array is 65.
The maximum value in the integer array is 84.

Please choose from the following options:

A) Print the values in the integer array.
B) Print the values in the character array.

C) Print the minimum/maximum values in the integer array.
D) Print the minimum/maximum values in the character array.

E) Search for a value in the integer array.
F) Search for a value in the character array.

Q) Quit.

Choice: F

Please enter a character to search for: t

The character e is not in the array.

Please choose from the following options:

A) Print the values in the integer array.
B) Print the values in the character array.

C) Print the minimum/maximum values in the integer array.
D) Print the minimum/maximum values in the character array.

E) Search for a value in the integer array.
F) Search for a value in the character array.

Q) Quit.

Choice: E

Please enter an integer to search for: 80

The integer 80 is in the array.

Please choose from the following options:

A) Print the values in the integer array.
B) Print the values in the character array.

C) Print the minimum/maximum values in the integer array.
D) Print the minimum/maximum values in the character array.

E) Search for a value in the integer array.
F) Search for a value in the character array.

Q) Quit.

Choice: Q