| |
Sorting Effectively in Java
This tutorial is generally about sorting in Java – ways to do it, and how to do it correctly, quickly, and effectively. This tutorial will use one problem, and shows the many approaches to do so.
Here’s the problem:
Suppose you’re to sort a list of books, given by the number of pages, and the initial of the author. The style of input is on one line, a number between 0 – 999 denoting the number of pages, a space, then the author’s initials with 2 uppercase letters.
We are to sort them by the number of pages, and then by the first, then last initials of the author.
The input will be given by one string, with one number denoting the number of books. We’re to implement a “bookOrder” method that returns the sorted string.
Input:
15 AB 219 AE 518 SE 518 AB 17 CE, 5
Output:
15 AB 17 CE 219 AE 518 AB 518 SE
Method 1
Because in competitions, this is timed, so one might write it very inefficently, using bubblesort:
import java.util.*;
public class Book{
public String bookOrder( String books, int number ){
int[] pages = new int[ number ];
String[] title = new String[ number ];
StringTokenizer st = new StringTokenizer( books );
for ( int i = 0; i < number; i++ ){
pages[i] = Integer.parseInt( st.nextToken() );
title[i] = st.nextToken();
}
for ( int i = 0; i < number; i++ ){
for ( int j = 0; j < number - 1; j++ ){
if ( pages[j] > pages[j+1] ||
( pages[j] == pages[j+1] && title[j].compareTo( title[j+1] ) > 0 ) ){
pages[j] ^= pages[j+1];
pages[j+1] ^= pages[j];
pages[j] ^= pages[j+1];
String temp = title[j];
title[j] = title[j+1];
title[j+1] = temp;
}
}
}
String s = "";
for ( int i = 0; i < number; i++ ){
s += (int)pages[i] + " " + title[i] + " ";
}
return s.trim();
}
}
|
The above method took about 5 minutes to write, is stable, but isn't very efficient. ( At O( n^2 ) )
This code is also very flexible, as you only need to change this statement to sort it differently:
if ( pages[j] > pages[j+1] ||
( pages[j] == pages[j+1] && title[j].compareTo( title[j+1] ) > 0 ) )
|
If we wanted to sort by initial first and then page number, we can easily modified this to:
if ( title[j].compareTo( title[j+1] ) > 0 ) ||
( title[j].compareTo( title[j+1] ) == 0 && pages[j] > pages[j+1] ) )
|
or changed the signs if we wanted to sort descendingly:
if ( pages[j] < pages[j+1] ||
( pages[j] == pages[j+1] && title[j].compareTo( title[j+1] ) > 0 ) )
|
Method 2
A better and more efficient way is to use the Java API. This is using a relatively underused class java.util.Arrays and the interface Comparable:
import java.util.*;
public class Book{
private class B implements Comparable {
int pages;
String title;
public B ( int p, String t ){
title = t;
pages = p;
}
public int compareTo( Object o ){
B k = (B) o;
if ( pages != k.pages ){
return pages - k.pages;
}
else
return title.compareTo( k.title );
}
}
public String bookOrder( String books, int number ){
B[] book = new B[ number ];
StringTokenizer st = new StringTokenizer( books );
for ( int i = 0; i < number; i++ ){
book[i] = new B(Integer.parseInt( st.nextToken() ), st.nextToken() );
}
Arrays.sort( book );
String s = "";
for ( int i = 0; i < number; i++ ){
s += (int)book[i].pages + " " + book[i].title + " ";
}
return s.trim();
}
}
|
This ensures that it runs in O( n * log n ) time, using a tuned quicksort. The best thing about writing
the code this way is that it's cleaner, and it's also less error-prone, if you let the API do the work.
Let's go over it in detail:
private class B implements Comparable
|
This is a private helper class. It implements Comparable so that we can sort it later.
public int compareTo( Object o ){
B k = (B) o;
if ( pages != k.pages ){
return pages - k.pages;
}
else
return title.compareTo( k.title );
}
|
This method is the method that does the comparing. Naturally, it returns a negative integer if this object is smaller, a zero if they're the same, and a positive interger if the specified Object is smaller.
This lets us sort anything, but it requires that all elements in the array be implementing the Comparable interface. That means if you're sorting just ints, or doubles, or Strings, this is very handy and let you get the work done quicker. Why reinvent the wheel, after all?
The above way is not that hard to implement, and it doesn't take too long, but generally requires me to remember too much syntax.
However, it is the preferable way to sort things in Java. Learning it helps a lot in sorting in general.
To modify what to sort, we simply modify the compareTo method:
public int compareTo( Object o ){
B k = (B) o;
if ( pages != k.pages ){
return pages - k.pages;
}
else
return title.compareTo( k.title );
}
|
as with method 1, if we wanted to sort descendingly:
public int compareTo( Object o ){
B k = (B) o;
if ( pages != k.pages ){
return k.pages - pages;
}
else
return title.compareTo( k.title );
}
|
or title first:
public int compareTo( Object o ){
B k = (B) o;
if ( title.compareTo( k.title ) != 0 )
return title.compareTo( k.title );
else
return pages - k.pages;
|
or title descendingly:
public int compareTo( Object o ){
B k = (B) o;
if ( title.compareTo( k.title ) != 0 )
return -1 * title.compareTo( k.title );
else
return pages - k.pages;
|
Method 3
So is there another alternative?
This requires us to think about the boundry conditions. Since Arrays.sort also sort Strings, we can format the entire thing as an Array of Strings, and then sort them:
import java.util.*;
public class Book{
public String bookOrder( String books, int number ){
StringTokenizer st = new StringTokenizer( books );
String[] book = new String[ number ];
for ( int i = 0; i < number; i++ ){
int pages = Integer.parseInt( st.nextToken() );
String title = st.nextToken();
book[i] = format( pages ) + title + pages + " " + title;
}
Arrays.sort( book );
String s = "";
for ( int i = 0; i < number; i++ ){
s += book[i].substring(5) + " ";
}
return s.trim();
}
String format ( int pages ){
String temp = "0000000" + pages;
return temp.substring( temp.length() - 3 );
}
}
|
The above works, is very short to write, and is pretty intuitive. In general, I recommend the second method, but usually I have to look up the syntax on an API, and the above saves me some time, and time is a very important constraint sometimes.
To modify what to sort, we simply modify the parsing line:
book[i] = format( pages ) + title + pages + " " + title;
|
to descending pages:
book[i] = format( 999 - pages ) + title + pages + " " + title;
|
to initials:
book[i] = title + format( 999 - pages ) + pages + " " + title;
|
to descending initials:
book[i] = (char) ('Z' - ( title.charAt(0) - 'A' )) + (char) ('Z' - ( title.charAt(1) - 'A' ) +
format( 999 - pages ) + pages + " " + title;
|
To test the above methods, we just need to add the main method:
public static void main( String[] args )
{
Book a = new Book();
System.out.println( a.bookOrder( "15 AB 219 AE 518 SE 518 AB 17 CE", 5 ) );
}
|
This was meant to be a quick tutorial to coders that already knows how to program, and to provide them alternative way of solving a problem quicker.
|
|