Introduction: Searching and Sorting
There’s all sorts of sorts in the programming world, from merge sort to bubble sort to insertion sort and selection sort. These sorts are commonly used algorithms used to order a group of objects based on a series of comparisons. We might see a natural ordering of objects like Integers, where they are arranged in ascending or descending order.
While it can be helpful to learn how to read and implement some of the sorts mentioned earlier, in this lab we will be working with the features Java has already built in for us, to see how inheritance can make using these tools easier.
Binary Search
You may think of a traditional search as going one by one systematically through some group of items to find the one you’re looking for. This is what we call a linear search within the programming world. It is the most basic search.
A Binary Search is a slightly more complex search method that is faster than a linear search, but it requires the set of objects you are searching to be sorted. It operates by reducing the amount of objects you are searching through by half on each iteration. In each iteration, the middle element of the interval is compared with the item to search for.
If the search item is less than the middle element, the next iteration’s set will be the lower half of the current set. If it is greater, then it will be the upper half. If the search item is equal to the middle element, then you’ve finished your search!
Collections
A Collection is a group of objects. In Java, many collections exist to store objects like lists, sets, maps, and many more. These have already been implemented for you, like Arrays and ArrayLists, and so they provide easy storage with associated methods that manipulate the objects inside them.
Two of the important methods associated with the Collections class that we will discuss in today’s labs are sort and binarySearch.
These two methods provide built-in means for searching for an object within a collection, or sorting an entire collection by the objects’ “natural ordering”, or a specific quality the programmer specifies.
Collections.binarySearch(List l, Object o) takes two parameters, a list that can be iterated through, and an object to search for within the list.
It returns an int specifying the index of the object if it is found within the list.
Collections.sort() takes a list of objects that have been instantiated using a class that implements the Comparable interface. It sorts those objects based on the compareTo method that is implemented within the class, if no other Comparator has been specified.
Comparable Interface
The Comparable provides the means to order objects of each class.
This ordering is dictated by comparisons between each object using the compareTo method for the class, which is considered the class’s “natural ordering”. The compareTo method might distinguish the object’s comparison value from a class variable that can be quantified.
The compareTo() method when called like this:
objectA.compareTo(objectB) returns an int that is:
- negative - if objectA is less than objectB
- zero - if objectA and objectB are equal
- positive - if objectA is more than objectB
To implement the Comparable interface, just add the keywords implements Comparable<> after declaring the class, including the class name inside the <>, and implement the compareTo() method in the class.
Then, when using a collection like described above, you may easily sort the objects using Collections.sort(collectionName).
Introduction to Today’s Lab
In today’s lab, you will be working with two classes, the csuRam and goRams classes.
The csuRam class represents a single CSU student. In the csuRam class, we have included:
- two class variables, a string called name and an int called id
- a static boolean called compareData that represents which class variable, name or ID, should be compared for the equals and compareTo methods
- a constructor that initializes the class variables
- an overloaded toString method for the class
The goRams class represents a group of CSU students. In the goRams class, we have included:
- the outline of the createRams method that reads the file contents in to the arrayList, a class variable that you will define
- a listFormat method that returns a readable formatted string of the arrayList class variable
As usual, you are encouraged to create a Main class where you should test your code.
Step 1: goRams.rams and goRams.createRams()
Part A: goRams.rams
Define an ArrayList of csuRam objects called rams that is a class variable.
Part B: goRams.createRams()
The createRams() method takes a String that gives the name of the file to read from. We have already defined a try-catch block and scanner.
Read the data from the file into the ArrayList rams that you defined in Part A. Each line has a single CSU student that should be used to create a csuRam object. The line contains the student’s first and last name, and then their nine digit ID number.
As you create each object, add it to rams.
Step 2: csuRams.compareTo()
Part A:
Add to the class declaration of csuRam so that it implements the Comparable interface.
Part B:
Now, implement the compareTo() method in the csuRam class.
You will need to include @Override before the method signature. This method takes a csuRam object as a parameter, and returns an int.
Refer to the explanation of the compareTo() method above. However, the csuRam’s compareTo method should compare objects based on one of the two class variables, depending on if the static boolean compareData is true or false.
If compareData is true, compare the objects based on the String parameter, name. If compareData is false, compare the objects based on their id numbers.
Step 3: csuRam.equals()
Implement the equals() method for the csuRam class. It takes an object as a parameter.
Here is a helpful outside resource for overriding the equals method of an object’s class.
First, check if the objects you are comparing are the same object by using == to compare them.
Then use instanceof to check if the object is an instance of csuRam. If it is not, return false. If it is, proceed.
Now, depending on the truth value of compareData, check if the objects are equal using either their name or id.
Step 4: goRams.sortList()
Complete the sortList() method in the goRams class. This method takes a String to check for as a parameter that is either “name” or “id”.
Set the static variable in csuRam depending on the value of the parameter.
Then use Collections.sort() to sort the class variable rams.
This method exists to streamline the process of sorting the arrayList depending on the field of the static variable, so that a user could sort the list with one line and a coherent parameter, “name” or “id”.
This methods code is given to you. Please make sure to look over this code. No additional code is needed.
Step 5: goRams.findTonyFrank()
Complete the findTonyFrank() method in the goRams class.
This method finds the index of the object with name parameter “Tony Frank” in the rams list.
First, to ensure we are checking for the proper index, sort the ArrayList rams by name using the method you defined in Step 4.
Then, create an object that has “Tony Frank” as the name so that we have an object to search for within the list.
Using Collections.binarySearch(), search for Tony Frank within the list and return the index that it finds.
Refer here for more examples with the binarySearch method, or here for the Collections Java Docs.
This methods code is given to you. Please make sure to look over this code. No additional code is needed.