Two sub-tasks that are frequently found in large applications are searching and
ID: 3797168 • Letter: T
Question
Two sub-tasks that are frequently found in large applications are searching and sorting. These tasks are common but not so common that they directly form part of a programming language. Instead, they are provided as library functions. The two are typically considered together for two reasons: First, many searching algorithms, like the binary and the interpolative search, require that the array or list in which they search be sorted or ordered. The second reason is more complex.
Sorting and searching functions ultimately compare array or list elements two at a time: are the elements the same and if not, which one comes first. The answer to this question is simple when the array or list elements are numbers or strings. However, when the array or list contains objects, the answer is not so straightforward. Objects are typically compared by comparing one or more of their attributes. But which ones?
When a general purpose searching and sorting library is created, the creator is faced with the problem of making it truly general. This implies that the library should be capable of dealing with numbers and with any object and with any set of attributes in that object. The solution is to require the user of the library functions to provide an ordering function. Given two objects from the array or list, the ordering function indicates if they are the same or which one comes first. It examines selected attributes within the object to make that determination. Based on the information provided by the ordering function, searching and sorting library functions can complete their tasks. Searching and sorting are typically considered together because they use the same ordering function.
The relationship between the three sections of code is illustrated at the right.
1. The user’s application calls the library code.
2. The searching and sorting library functions repeatedly call the user’s ordering function.
3. The user’s application, however, never directly calls the ordering function.
There are two ways to create the ordering function in a Java program:
1.implement the Comparable interface (in java.lang) and define a compareTo method; this implements the class’s “natural ordering”
2. create a new “helper” class that implements the Comparator interface (in java.util) and define the compare method
Assignment
Follow the Widget / WareHouse example program.
1. Create a public class Person that implements the Comparable interface
a. Instance V ariables
private int id;
private String name;
private String street;
private String city;
private String state;
private String phoneNumber;
b. Constructors:
i. public Person(int num,String n,String s,String c, String st, String p)
ii. public Person(String n) (initialize the name and sets the other values to null or 0 as appropriate)
iii. public Person(int n) (initialize the id number and sets the other values to null)
c. Methods
i. publicStringtoString()(whichconcatenatesallPersoninstance variables)
ii. public int getID() (accessor method for the id instance variable)
d. The Comparable Interface
i. Comparable is a generic interface (as of Java 5): Comparable<Person>
ii. public int compareTo(Person person)
iii. Compare two Person objects by name using the String compareTo method (this is done in your compareTo method) your method should return the value returned by the String method
2. Create a class named CompareInt
a. implements java.util.Comparator<Person> (see p. 212)
b. Defines a single method: public int compare(Person p1, Person p2) that compares two Person objects by id (call the getID method defined in class Person)
3. Complete the SortPerson.java class below (edit points are noted with comments). ReviewthesortandbinarySearchmethodsdefinedinboththeArrays and Collections classes of the util package and use the appropriate class to complete the assignment. Be sure to read the comments at the top of the file.
a. Use (i.e., call) the sort method to sort the list of Person objects alphabetically by name (use the single parameter sort method)
b. Use the class binarySearch method to search for a name entered on the command line. The method requires two parameters: the list and the key. The key is a Person object that only contains a name
c. Call the sort method to sort the list of Person objects numerically by id (use the two parameter version; the first is an list and the second is a comparator)
d. Use the binarySearch method to search for an id entered on the command line. The method requires three parameters: the list to search, a key, and the comparator
// Run the following main like this:
// java SortPerson "Isaac Newton" 301
// Note that the quotation marks are required!
//
// Setting Command Line Arguments in the Eclipse IDE:
// 1. "Run" (top menu) -> "Run Configurations..."
// 2. Select the "(x)= Arguments" tab
// 3. Add the command line arguments in the "Program arguments:" text area
// 4. Press "Apply"
import java.util.*;
public class SortPerson
{
private ArrayList<Person> people = new ArrayList<Person>();
public SortPerson()
{
people.add(new Person(301, "Albert Einstein", "123 My Street", "Your Town", "UT", "123-4567"));
people.add(new Person(860, "John Smith", "867 Elm St.", "Lake Forest", "AZ", "555-6543"));
people.add(new Person(51, "Cranston Snort", "1600 Pennsylvania Ave", "Washington", "DC", "1-800-123-4783"));
people.add(new Person(602, "Fred Wally", "123 E. Wilson", "Sunset", "UT", "678-4351"));
people.add(new Person(857, "Isaac Newton", "1234 W. 900 S.", "Salt Lake City", "UT", "563-4567"));
people.add(new Person(403, "Wilson", "1492 USA Way", "Morristown", "NJ", "345-8765"));
people.add(new Person(4567, "John Smith", "417 El Toro", "Irvine", "CA", "869-3482"));
}
public void sortByName(String name)
{
// sort list people by name here
____________________________________
for (Person p : people) // print sorted list
System.out.println(p);
System.out.println(" Searching for:");
// make key based on search name
__________________________________________
// add natural (by name in this case) search code here
__________________________________________
if (index >= 0)
System.out.println(people.get(index));
else
System.out.println(name + " was not found");
System.out.println(); // print a blank line
}
public void sortByID(int id)
{
// make a int-based compartor here
____________________________________
// sort list people by id here
____________________________________
for (Person p : people) // print sorted list
System.out.println(p);
System.out.println(" Searching for:");
// make key based on id
_____________________________________
// add comparator-based search code here
if (index >= 0)
System.out.println(people.get(index));
else
System.out.println(id + " was not found");
}
public static void main(String args[])
{
SortPerson sp = new SortPerson();
sp.sortByName(args[0]);
sp.sortByID(Integer.parseInt(args[1]));
}
}
Explanation / Answer
import java.util.*;
public class SortPerson
{
private ArrayList<Person> people = new ArrayList<Person>();
public SortPerson()
{
people.add(new Person(301, "Albert Einstein", "123 My Street", "Your Town", "UT", "123-4567"));
people.add(new Person(860, "John Smith", "867 Elm St.", "Lake Forest", "AZ", "555-6543"));
people.add(new Person(51, "Cranston Snort", "1600 Pennsylvania Ave", "Washington", "DC", "1-800-123-4783"));
people.add(new Person(602, "Fred Wally", "123 E. Wilson", "Sunset", "UT", "678-4351"));
people.add(new Person(857, "Isaac Newton", "1234 W. 900 S.", "Salt Lake City", "UT", "563-4567"));
people.add(new Person(403, "Wilson", "1492 USA Way", "Morristown", "NJ", "345-8765"));
people.add(new Person(4567, "John Smith", "417 El Toro", "Irvine", "CA", "869-3482"));
}
public void sortByName(String name)
{
// sort list people by name here
____________________________________
for (Person p : people) // print sorted list
System.out.println(p);
System.out.println(" Searching for:");
// make key based on search name
__________________________________________
// add natural (by name in this case) search code here
__________________________________________
if (index >= 0)
System.out.println(people.get(index));
else
System.out.println(name + " was not found");
System.out.println(); // print a blank line
}
public void sortByID(int id)
{
// make a int-based compartor here
____________________________________
// sort list people by id here
____________________________________
for (Person p : people) // print sorted list
System.out.println(p);
System.out.println(" Searching for:");
// make key based on id
_____________________________________
// add comparator-based search code here
if (index >= 0)
System.out.println(people.get(index));
else
System.out.println(id + " was not found");
}
public static void main(String args[])
{
SortPerson sp = new SortPerson();
sp.sortByName(args[0]);
sp.sortByID(Integer.parseInt(args[1]));
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.