Java Sorting-java sorting algorithms

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 );

   // Parsing
   for ( int i = 0; i < number; i++ ){
       pages[i] = Integer.parseInt( st.nextToken() );
       title[i] = st.nextToken();
   }

   // Bubblesort
   for ( int i = 0; i < number; i++ ){
       for ( int j = 0; j < number - 1; j++ ){
       // This does the actual comparison
       if ( pages[j] > pages[j+1] ||
           ( pages[j] == pages[j+1] && title[j].compareTo( title[j+1] ) > 0 ) ){
           // Swapping
           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;
       }
       }
   }

   // Returns it in the format required.    
   String s = "";
   for ( int i = 0; i < number; i++ ){
       s += (int)pages[i] + " " + title[i] + " ";
   }
   // trim() trims the trailing ( and leading spaces ) in a string.
       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 {
   // Fields to be sorted
   int pages;
   String title;
  
   // Initializer
   public B ( int p, String t ){
       title = t;
       pages = p;
   }
  
   // The required 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 );
   }
   }

   public String bookOrder( String books, int number ){
   B[] book = new B[ number ];
   StringTokenizer st = new StringTokenizer( books );

   // Parsing
   for ( int i = 0; i < number; i++ ){
       book[i] = new B(Integer.parseInt( st.nextToken() ), st.nextToken() );
   }
  
   // Using Arrays.sort
   Arrays.sort( book );
  
   // Return it in the format required.
   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.

Arrays.sort( Object[] )

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 ];

   // Parsing
   for ( int i = 0; i < number; i++ ){
       int pages = Integer.parseInt( st.nextToken() );
       String title = st.nextToken();

        /** Format is as following:

         * DDDTTNNNNN
         * Where DDD is the number of pages
         * TT is the initials
         * and NNNNN is the original string
         **/

       book[i] = format( pages ) + title + pages + " " + title;
   }
  
   // Using Arrays.sort
   Arrays.sort( book );
  
   String s = "";
   for ( int i = 0; i < number; i++ ){
   // Why 5?  the first 5 characters are throw away letters to be sorted
       s += book[i].substring(5) + " ";
   }
   return s.trim();
   }

   // This pads the number of pages with zeros.
   String format ( int pages ){
   String temp = "0000000" + pages;
   // Why 3?  Since it only goes up to 999, we only need the last 3 digits.
   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.
http://devhood.com/Tutorials/tutorial_details.aspx?tutorial_id=395

Java Sorting

Sorting Effectively in Java

0 comments:

Post a Comment