CPE 102 Lab 7 - Sorting and Searching
Goals:

Orientation:

In this lab you will write two classes, one will sort an ArrayList<String> and the other will search an ordered ArrayList<String> using a Binary Search.

What To Do:
  1. Below you will find a class called SelectionSorter (similar to one found in our text on page 629 in the thrid edition, page 597 in the fourth edition). Change the instance variable from an int array to an ArrayList<String> and then make all the necessary code changes to support this modification. Among other things, you will need to use the compareTo method of the String class instead of the relational operators that are used to compare primitive integers in the provided code. Be sure to test your solution to make sure it is working. You need to write a driver that sorts the file in randomWords.zip or create your own input for testing, which ever you prefer. Note that as long as you make a shallow copy of the ArrayList in SelectionSorter's constructor you'll be able to access the reordered version through the reference you passed to the constructor. I suggest writing a test driver with a method that verifies the ArrayList is correctly ordered after calling sort - you can use the compareTo method of the String class to verify the ordering.
        public class SelectionSorter
        {
           private int[] a;

           public SelectionSorter(int[] array)
           {
              this.a = array;
           }

           public void sort()
           {
              for (int i = 0; i < a.length - 1; i++)
              {
                 int minPos = minimumPosition(i);
                 swap(minPos, i);
              }
           }

           private int minimumPosition(int from)

           {
              int minPos = from;

              for (int i = from + 1; i < a.length; i++)
              {
                 if (a[i] < a[minPos])
                 {
                    minPos = i;
                 }
              }

              return minPos;
           }

           private void swap(int i, int j)
           {
              int temp = a[i];
              a[i] = a[j];
              a[j] = temp;
           }
        } // End of class

  1. Below you will find a class called BinarySearcher (similar to one found in our text on page 652 in the third edition, page 617 in the fourth edition). Change the instance variable form an int array to an ArrayList<String> and then make all the necessary code changes to support this modification. Among other things, you will need to use the compareTo method of the String class instead of the relational operators that are used to compare primitive integers in the proviede code. You your code from part one to make a driver that will search through the random words in part 1. You must use an ordered list for the binary search algoritm to work.

        public class BinarySearcher
        {
            private int[] a;

            public BinarySearcher(int[] array)
            {
                this.a = array;
            }

            public int search(int value)
            {
                int lo = 0;
                int hi = a.length - 1;

                while (lo <= hi)
                {
                    int mid = (lo + hi) / 2;
            
                    if (value < a[mid])
                    {
                        hi = mid - 1;
                    }
                    else if (value > a[mid])
                    {
                        lo = mid + 1;
                    }
                    else
                    {
                        return mid;
                    }
                }

                return -1;

            }

        } // End of class

Lab courtesy of Kurt Mammen.