You will write 3 new methods in the ArrayBag class:
bubbleSort - a method to sort the array in ascending order using the bubble sort
binarySearchIterative – a repetitive version of the binary search
binarySearchRecursive - a recursive version of the binary search (You should use a helper method that calls the recursive method so the client code does not have to provide the extra parameters. Client calls to both of the search methods should be identical other than the method name.)
Load your bag with some initial values, but do not fill it completely.
Your client code should give the user the option to:
display the contents of the bag using the class method “toVector”
add values to the bag
remove values from the bag
sort the bag
search for a value using their choice of either the iterative search or the recursive search - both need to be tested
Allow the user to keep doing these things until they are done.
Do not automatically sort the bag if the user chooses to search. Your program should give the user a message telling them they must first sort the bag before they can search. You must think of a way to detect programatically that the array has not been sorted.
You decide what the user interface will be. Make it clear and easy to use. It can be very basic; nothing fancy. A menu driven program works well.
Each value in your array should be unique - no value will appear in the array multiple times.
Your array elements can be any data type the client code wants to use – use a template class put in place in the code provided. You can write your client code to process a bag holding any data type you want.
Write your client code in a modular, structured fashion. Make sure you perform input validation where appropriate. This program should be bullet-proof and well documented. I am expecting code from a programmer who is in their third semester of writing software.
Including:
Program description (comment block at top of program)
Function descriptions for every function other than main() (see function heading below)
Comments at major algorithm steps (at a minimum)
Followed directions
Correct output
Structured program design
Meaningful identifier names
Function heading should look similar to this:
/******************************************************************************/
/* Function: functionName
/* Inputs: parameters passed and what they represent
/* Outputs: value(s) returned via return statemen or
/* on the parameter list
/* Purpose: This function blah blah blah….. describing what
/* the function does
/******************************************************************************/
NOTE – The “NEVER” list of rules:
You will NEVER use break, exit, return, pass, continue or anything to leave a loop (or iteration), function, or other construct prematurely, unless it is part of the structure as in a case statement.
You will NEVER have a function call itself, unless it is intentional recursion.
You will NEVER use global variables. However, you may use global constants if it is appropriate and they are used properly.
You will have only one return statement in a function. (Exception – Multiple return statements may be necessary in a recursive function.)