Girl in IT-wolrd

Everything has been downloaded. Quit download loop.

Sorting in Java

In this section we discuss four different ways to sort data in Java.

Arrays of primitives

An array of primitives is sorted by direct invocation of Arrays.sort method

int[] a1 = {3,4,1,5,2,6};
Arrays.sort(a1);

Arrays of objects

In order to sort an array of abstract object, we have to make sure that objects are mutually comparable. The idea of comparable is extension of equals in a sence than we need to know not only that two objects are not equal but which one is larger or smaller. This is supported by the Comparable interface. This interface contains only one method with the following signature:

	public int compareTo(Object obj);

The returned value is negative, zero or positive depending on whether this object is less, equals or greater than parameter object. Note a difference between the equals() and compareTo() methods. In the following code example we design a class of playing cards that can be compared based on their values:

class Card implements Comparable<Card>
{
   private String suit;
   private int value;

   public Card(String suit, int value)
   {
      this.suit = suit;
      this.value = value;
   }
   public int getValue()
   {
      return value;
   }
   public String getSuit()
   {
      return suit;
   }
   public int compareTo(Card x)
   {
      return getValue() - x.getValue();
   }
}

Suppose that the Card class implements the Comparable interface, then we can sort a group of cards by envoking by Arrays.sort method.

Card[] hand = new Card[5];
Random rand = new Random();
for (int i = 0; i ‹ 5; i++)
	hand[i] = new Card(rand.nextInt(5), rand.nextInt(12));
Arrays.sort(hand);

It is important to recognize that if a class implements the Comparable interface than compareTo() and equals() methods must be correlated in a sense that if x.compareTo(y)==0, thenx.equals(y)==true. The default equals() method compares two objects based on their reference numbers and therefore in the above code example two cards with the same value won’t be equal. And a final comment, if the equals() method is overriden than the hashCode() method must also be overriden, in order to maintain the following properety: if x.equals(y)==true, thenx.hashCode()==y.hashCode().

Collection of comparable objects

Mutually comparable objects in a collection are sorted by Collections.sort method:

ArrayList‹Integer> a2 = new ArrayList‹Integer> (5);
...
Collections.sort(a2);

Comparator

The Comparable interface does not provide a complete solution. The main problem is that the above code works only for objects that have that particular implementation of the compareTo method. Once you implemented compareTo , you don’t have much flexibility. Moreover, it is not always possible to decide on a “correct” meaning for compareTo. This method can be based on many different ideas. The solution to this problem is to pass the comparison function as a parameter. Such comparison function in Java is implemented as the Comparator interface. Consider a poker hand: to do a fast evaluation you want to sort your cards either by value or by suit. The way to support these two different criterias is to create two classes SortByValue and SortBySuit that implementsComparator interface

class SuitSort implements Comparator
{
   public int compare(Object x, Object y)
   {
      int a = ((Card) x).getSuit();
      int b = ((Card) y).getSuit();

      return a-b;
   }
}

and then pass a comparison function into a sorting routine. In Java, you cannot pass a method; you should wrap a class around it.

Arrays.sort(hand, new SuitSort());

This new object SuitSort is called a functor, and the style of programming is called a functional programming. The functor is a simple class which usually contains no data, but only a single method. We can design different comparison functions by simply declaring new classes, one class for each kind of functionality. An instance of this class (which implements the interface) is passed to algorithm, which in turn calls the method from the function object.

See SortDemo.java and SortDemo2.java for implementation details.

SortDemo.java

/*****************************************************************************
 *    This demonstrates soring in Java
 *
 *****************************************************************************/

import java.util.*;

public class SortDemo
{
//@SuppressWarnings("unchecked")
	public static void main(String[] args)
	{
		//sort an array of strings using natural ordering
		String[] words1 = {"Fred","bob","Tom","Mark","john","Steve"};
		Arrays.sort(words1);
		System.out.println(Arrays.toString(words1));

		String[] words2 = {"Fred","bob","Tom","Mark","john","Steve"};
		Arrays.sort(words2, new Comp1());
		System.out.println(Arrays.toString(words2));

		//sort in reverse order
		String[] words3 = {"Fred","Bob","Tom","Mark","John","Steve"};
		Arrays.sort(words3, new Comp2());
		System.out.println(Arrays.toString(words3));

		//sort by emails
		String[] words4 = {"Fred@cmu.edu","Bob@yahoo.com",
		"Tom@gmail.com","Mark@ucla.edu","John@pit.edu","Steve@microsoft.com"};
		Arrays.sort(words4, new Comp3());
		System.out.println(Arrays.toString(words4));
    }
}

class Comp1 implements Comparator<String>
{
	public int compare(String obj1, String obj2)
	{
		return obj1.compareToIgnoreCase(obj2);
	}
}

class Comp2 implements Comparator<String>
{
	public int compare(String obj1, String obj2)
	{
		return obj2.compareTo(obj1);
	}
}

class Comp3 implements Comparator<String>
{
	public int compare(String obj1, String obj2)
	{
		String str1 = obj1.substring( obj1.indexOf("@") );
		String str2 = obj2.substring( obj2.indexOf("@") );
		return str1.compareToIgnoreCase(str2);
	}
}

SortDemo2.java

/*****************************************************************************
 *      Demonstrates Comparable and Comparator interfaces
 *
 *****************************************************************************/
import java.util.*;

public class SortDemo2
{
	public static void main(String[] args)
	{
		//sort an array of cards by using the Comparable interface
		String[] suits = {"Diamonds", "Hearts", "Spades", "Clubs"};
		Card[] hand = new Card[5];
		Random rand = new Random();;

		for (int i = 0; i < 5; i++)
			hand[i] = new Card(suits[rand.nextInt(4)], rand.nextInt(12));

		System.out.println("(suit, value):  ");
		System.out.println(Arrays.toString(hand));

		System.out.println("\nsort by value");
		Arrays.sort(hand);
		System.out.println(Arrays.toString(hand));

		//sort an array of cards by using the Comparator
		Arrays.sort(hand, new SuitSort());
		System.out.println("\nsort by suit");
		System.out.println(Arrays.toString(hand));

		/*  TREESET  */
		for (int i = 0; i < 5; i++)
			hand[i] = new Card(suits[rand.nextInt(4)], rand.nextInt(12));

		System.out.println("(suit, value):  ");
		System.out.println(Arrays.toString(hand));
		System.out.println();

		//cards with the same value collide
		TreeSet<Card> tree1 = new TreeSet<Card>();
		for (int i = 0; i < 5; i++) tree1.add( hand[i] );
		System.out.println(tree1);
		System.out.println();

		//cards with the same suit collide
		TreeSet<Card> tree2 = new TreeSet<Card>( new SuitSort() );
		for (int i = 0; i < 5; i++) tree2.add( hand[i] );
		System.out.println(tree2);
		System.out.println();

		//no collisions
		TreeSet<Card> tree3 = new TreeSet<Card>( new SuitValue() );
		for (int i = 0; i < 5; i++) tree3.add( hand[i] );
		System.out.println(tree3);
		System.out.println();
    }
}

class Card implements Comparable<Card>
{
	private String suit;
	private int value;

	public Card(String suit, int value)
	{
		this.suit = suit;
		this.value = value;
	}
	public int getValue()
	{
		return value;
	}
	public String getSuit()
	{
		return suit;
	}
	public String toString()
	{
		return "(" + suit + "," + value +")";
	}
	public int compareTo(Card x)
	{
		return getValue() - x.getValue();
	}
}

class SuitSort implements Comparator<Card>
{
	public int compare(Card x, Card y)
	{
		return x.getSuit().compareTo( y.getSuit() );
	}
}

class SuitValue implements Comparator<Card>
{
	public int compare(Card x, Card y)
	{
		int n = x.getSuit().compareTo( y.getSuit() );
		if( n != 0 )
			return n;
		else
			return x.getValue() - y.getValue();
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: