Searching and Sorting In An Integer List

• IntegerList(int size) -- creates a new list of size elements. Elements are initialized to 0.
• void randomize() -- fills the list with random integers between 1 and 100, inclusive.
• String toString() -- returns a string representation of the array elements and indices
• int search(int target) -- looks for value target in the list using a sequential search algorithm. Returns the index where it first appears if it is found, -1 otherwise.
• void selectionSort() -- sorts the lists into ascending order using the selection sort algorithm.

  File IntegerListTest.java contains a Java program that provides "menu-driven" testing for the IntegerList class. Copy both files to your directory, and compile and run IntegerListTest to see how it works. For example, create a list, print it, and search for an element in the list. Does it return the correct index? Now look for an element that is not in the list. Is the return vaue correct? Now sort the list and print it to verify that it is in sorted order.

  Modify the code in these files as follows:

  1. Add a method void sortDecreasing() to the IntegerList class that sorts the list into decreasing (instead of increasing) order. Use the selection sort algorithm, but modify it to sort the other way. Alternatively, you could have this method call selectionSort, then reverse the array.

     Add an option to the menu in IntegerListTest to test your new method. (You'll have to modify both the printMenu and dispatch methods.) Add to your lab document output showing the use of the menu to reverse sort an originally unsorted array.

  2. Add a method void replaceFirst(int oldVal, int newVal) to the IntegerList class that replaces the first occurrence of oldVal in the list with newVal. If oldVal does not appear in the list, it should do nothing (but it's not an error). If oldVal appears multiple times, only the first occurrence should be replaced. Note that you already have a method (search) to find oldVal in the list; use it!

     Add an option to the menu in IntegerListTest to test your new method. The action associated with the menu item should prompt the user to enter the old and new values. Add to your lab document output showing the use of the menu to replace an element in an array.

  3. Add a method void replaceAll(int oldVal, int newVal) to the IntegerList class that replaces all occurrences of oldVal in the list with newVal. If oldVal does not appear in the list, it should do nothing (but it's not an error). Does it still make sense to use the search method like you did for replaceFirst, or should you do your own searching here? Consider the efficiency of your solution--you should try to write code that solves its job as quickly as possible.

  Add an option to the menu in IntegerListTest to test your new method. The action associated with the menu item should prompt the user to enter the old and new values. Add to your lab document output showing the use of the menu to replace all of one copy of an element in an array. (You may have to generate several arrays to create one with at least one duplicate entry.)

What to turn in