CPSC 170 Lab 1: Searching and Sorting

File IntegerList.java contains a Java class representing a list of integers. This is very similar to the IntegerList class we discussed in class. The following public methods are provided:

• 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.
• int seqSearch(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.
• int binarySearch(int target) -- looks for value target in the list using a binary search algorithm. Assumes that list has been sorted into ascending order. Returns the index where target is found if it appears in the list, -1 otherwise. Note that binarySearch is not guaranteed to return the first occurrence.
• 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 use sequential search to look for an element in the list. Does it return the correct index? Now look for an element that is not in the list. Now sort the list, print it to verify that it is in sorted order, and search for the same elements using binary search. Note that binary search won't work if you don't sort the list first!

  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. Be sure you change the variable names so they make sense!

     Add an option to the menu in IntegerListTest to test your new method.

  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 to find oldVal in the list; use it!

     Add an option to the menu in IntegerListTest to test your new method.

  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? Think about this.

     Add an option to the menu in IntegerListTest to test your new method.

  4. Add a method void addElement(int newVal) to the IntegerList class that adds an element to the list. Since the array is already full, we will have to create a new, bigger array. So you'll need to do the following:
     1. Create a new array that is one longer than the old array.
     2. Copy everything from the old array to the new array.
     3. Put the new value at the end of the new array.
     4. Make list refer to the new array.
     Add an option to the menu in IntegerListTest to test your new method.

  5. Add a method void removeFirst(int newVal) to the IntegerList class that removes the first occurrence of a value from the list. If the value does not appear in the list, it should do nothing (but it's not an error). Since the array needs to stay full, if the element is there to be removed we will have to create a new, smaller array. So you'll need to do the following:
     1. Create a new array that is one shorter than the old array.
     2. Copy everything except the first occurrence of the value given from the old array to the new array.
     3. Make list refer to the new array.
     Add an option to the menu in IntegerListTest to test your new method.

  6. Add a method removeAll(int newVal) to the IntegerList class that removes all occurrences of a value from the list. If the value does not appear in the list, it should do nothing (but it's not an error). Note that you'll have to figure out how big the new array should be before you create it.

     Add an option to the menu in IntegerListTest to test your new method.

  7. Add a method void addInOrder(int newVal) to the IntegerList class that assumes that the list is sorted in increasing order and adds the given element in its correct (sorted) position. So if the list contained the values 10 20 30 40 50 and you added 25, the new list would be 10 20 25 30 40 50. Don't just stick the value on the end and then sort! Sorting is expensive -- actually look through the list, figure out where the new value should go, and put it there. Note that you are increasing the size of the list at the same time.

     Add an option to the menu in IntegerListTest to test your new method.

  HAND IN:

  • Printouts of each IntegerList.java and IntegerListTest.java.
  • Tar the files in your lab1 directory and email the .tgz file to me (bloss@cs.roanoke.edu).