Sorting Arrays

When displaying output in a program it is often beneficial to sort the information alphabetically or numerically.
The Java language has an interface called java.util.Comparator which has two important functions called "compare"
and "equals" which need to be overrided in order for sorting to take place. The java.util.Arrays static "sort"
function is used with parameters of array and Comparator in order to sort an array. The description from
javadocs for Arrays.sort includes the following identifying origins of the "sort" function:
"The implementation was adapted from Tim Peters's list sort for Python ( TimSort). It uses techniques from Peter McIlroy's "Optimistic Sorting and Information Theoretic Complexity", in Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, pp 467-474, January 1993."
Here is an example:
import java.util.Comparator; import java.util.Vector; import java.util.Arrays; import java.io.BufferedReader; import java.io.InputStreamReader; class SortTelephoneNumbers { public static void main(String args[]) { try { SortTelephoneNumbers udtSTN=new SortTelephoneNumbers(); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); Vector vecContacts=new Vector(); do { System.out.println("Type in \"new\" if you want to enter a new contact or type in \"list\" if you want to see a list or type \"exit\" to exit the program."); String strNextOperation=br.readLine(); if(strNextOperation.equals("new")) { System.out.println("Enter the contact's name:"); String strName=br.readLine(); System.out.println("Enter the contact's phone number:"); String strTelephoneNumber=br.readLine(); SortTelephoneNumbers.TelephoneContact nextContact=udtSTN.new TelephoneContact(strName, strTelephoneNumber); vecContacts.addElement(nextContact); System.out.println(""); } else if(strNextOperation.equals("list")) { SortTelephoneNumbers.TelephoneContact contacts[]=new SortTelephoneNumbers.TelephoneContact[vecContacts.size()]; for(int i=0;i<vecContacts.size();i++) { contacts[i]=(SortTelephoneNumbers.TelephoneContact)vecContacts.elementAt(i); } Arrays.sort(contacts, udtSTN.new TelephoneContactComparator()); System.out.println("Contact List:"); System.out.println("Format: <name>:<number>"); for(int i=0;i<contacts.length;i++) { System.out.println(contacts[i].getName()+":"+contacts[i].getTelephoneNumber()); } System.out.println(""); } else if(strNextOperation.equals("exit")) { break; } } while(true); } catch(Exception ex) { ex.printStackTrace(); } } class TelephoneContact { String strName; String strTelephoneNumber; TelephoneContact(String strName, String strTelephoneNumber) { this.strName=strName; this.strTelephoneNumber=strTelephoneNumber; } public String getName() { return strName; } public String getTelephoneNumber() { return strTelephoneNumber; } } class TelephoneContactComparator implements Comparator { TelephoneContactComparator() { } public int compare(Object obj1, Object obj2) { TelephoneContact objTC1=(TelephoneContact)obj1; TelephoneContact objTC2=(TelephoneContact)obj2; return objTC1.strName.compareTo(objTC2.strName); } public boolean equals(Object obj) { return false; } } }
In the example, scroll down to "public int compare" to view the code that will do the sorting of our array. Instead of writing our own sorting code we make use of String's implementation of the function "compareTo". In most situations you will be able to do the same thing with another classes internal implementations of functions. If you are sorting numerically then use the Java operators less than("<"), greater than(">"), and equal to("=="). Here is an example:
import java.util.Comparator; import java.util.Hashtable; import java.util.Iterator; import java.util.Map; import java.util.Arrays; import java.io.BufferedReader; import java.io.InputStreamReader; class SortJobs { public static void main(String args[]) { try { SortJobs udtSJ=new SortJobs(); BufferedReader br=new BufferedReader(new InputStreamReader(System.in)); Hashtable hshContacts=new Hashtable(); do { System.out.println("Type in \"new\" if you want to enter a new worker"); System.out.println("Type in \"jobs\" if you want to add to the # of jobs that a worker has completed"); System.out.println("Type in \"list\" if you want to see a list"); System.out.println("Type in \"exit\" to exit the program"); String strNextOperation=br.readLine(); if(strNextOperation.equals("new")) { System.out.println("Enter the worker's name:"); String strName=br.readLine(); System.out.println("Enter the worker's phone number:"); String strTelephoneNumber=br.readLine(); SortJobs.JobContact nextContact=udtSJ.new JobContact(strName, strTelephoneNumber); hshContacts.put(strName, nextContact); System.out.println(""); } else if(strNextOperation.equals("jobs")) { System.out.println("Enter the worker's name:"); String strName=br.readLine(); System.out.println("Enter the number of jobs completed:"); String strJobsCompleted=br.readLine(); int intJobsCompleted=Integer.parseInt(strJobsCompleted); SortJobs.JobContact contact=(SortJobs.JobContact)hshContacts.get(strName); contact.setJobsCompleted(contact.getJobsCompleted()+intJobsCompleted); System.out.println(""); } else if(strNextOperation.equals("list")) { SortJobs.JobContact contacts[]=new SortJobs.JobContact[hshContacts.size()]; Iterator iter0=hshContacts.entrySet().iterator(); int intCountI=0; while(iter0.hasNext()) { Map.Entry mEntry=(Map.Entry)iter0.next(); contacts[intCountI++]=(SortJobs.JobContact)mEntry.getValue(); } Arrays.sort(contacts, udtSJ.new JobContactComparator()); System.out.println("Contact List:"); System.out.println("Format: <name>:<number>:<jobs completed>"); for(int i=0;i<contacts.length;i++) { System.out.println(contacts[i].getName()+":"+contacts[i].getTelephoneNumber()+":"+contacts[i].getJobsCompleted()); } System.out.println(""); } else if(strNextOperation.equals("exit")) { break; } } while(true); } catch(Exception ex) { ex.printStackTrace(); } } class JobContact { String strName; String strTelephoneNumber; int intJobsCompleted=0; JobContact(String strName, String strTelephoneNumber) { this.strName=strName; this.strTelephoneNumber=strTelephoneNumber; } public String getName() { return strName; } public String getTelephoneNumber() { return strTelephoneNumber; } public int getJobsCompleted() { return intJobsCompleted; } public void setJobsCompleted(int intJobsCompleted) { this.intJobsCompleted=intJobsCompleted; } } class JobContactComparator implements Comparator { JobContactComparator() { } public int compare(Object obj1, Object obj2) { JobContact objJC1=(JobContact)obj1; JobContact objJC2=(JobContact)obj2; if(objJC1.getJobsCompleted()<objJC2.getJobsCompleted()) return -1; else if(objJC1.getJobsCompleted()>objJC2.getJobsCompleted()) return 1; return 0; } public boolean equals(Object obj) { return false; } } }
In the above example, the workers are sorted according to how many jobs they have completed. With this implementation of Comparator's "compare" function the worker's are sorted in ascending order with the lowest number of jobs completed listed first in the list. If you want to sort them in descending order then just switch out the < for a > and vice versa in the "compare" function. In this lesson, you learned about sorting data in lists. You examined the java.util.Comparator's "compare" function and practiced with a java.util.Vector(using "addElement" and "elementAt") and a java.util.Hashtable(using "put" and "get" and creating a java.util.Iterator to iterate through the map).