Tuesday Jun 10, 2008

Avoid Array Sorting API for small list ?

All my personnel opinion, so can be wrong. But I have not found Array.sort very efficient for small lists and yes, it is not meant for small array list as well. I have written one small code where I have compared Sort API with the worst of all sorting algorithm, that is, bubble sort. Here is the code:

import java.util.\*;
public class BubbleSort {

	public static void main(String[] args) {
		int numbers[] = {10,20,5,14,1,56,0,56,56,3,2,5,466457,765,34,5,346,45676,23435,767,2545,62432,3,2,33,3,3,6,78,8,3435,7,3454567,35,50};
		int numbers1[] = {10,20,5,14,1,56,0,56,56,3,2,5,466457,765,34,5,346,45676,23435,767,2545,62432,3,2,33,3,3,6,78,8,3435,7,3454567,35,50};
		int length = numbers.length;
		long startTime1 = System.nanoTime();
		sortIt(numbers,length);
		long endTime1 = System.nanoTime();
		System.out.println("Time taken in Sorting  : " + (endTime1-startTime1)+ " nanoseconds"); 
		showIt(numbers);
		long startTime2 = System.nanoTime();
		sortbyAPI(numbers1);
		long endTime2 = System.nanoTime();
		System.out.println("Time taken in Sorting  : " + (endTime2-startTime2)+ " nanoseconds"); 
		showIt(numbers);
	}

	public static void sortIt(int numbers[], int length) {
		int temp;
		for(int i=length-1;i>=0;i--) {
			for(int j=1;j<=i;j++) {
				if(numbers[j-1]>numbers[j]) {
					temp = numbers[j-1];
					numbers[j-1] = numbers[j];
					numbers[j] = temp;
				}
			}
		}
	}

	public static void showIt(int numbers[]) {
		for(int i=0;i<numbers.length;i++) {
			System.out.print(numbers[i] + "    ");
		}
	}
	
	public static void sortbyAPI(int numbers[]) {
		Arrays.sort(numbers);
	}
} 

This are very clear from output:

E:\\Program Files\\Java\\jdk1.6.0\\bin\\SoringPrograms>java BubbleSort

Time taken in Sorting : 90514 nanoseconds

0 1 2 2 3 3 3 3 5 5 5 6 7 8 10 14 20 33 34 35 50 56 56 56 78 346 765 767 2545 3435 23435 45676 62432 466457 3454567

Time taken in Sorting : 190527 nanoseconds

0 1 2 2 3 3 3 3 5 5 5 6 7 8 10 14 20 33 34 35 50 56 56 56 78 346 765 767 2545 3435 23435 45676 62432 466457 3454567

I have decided to check the code in OpenJDK(\\src\\share\\classes\\java\\util\\Arrays.java). And I find lot of interesting things there:

- The sorting algorithm is a tuned quicksort (written in the documentation)

- In the real code, for short array, Insertion sort has been used, for big array pseudomedian  and so many thing ..

- It means it should be fast for any sorting array, but not the case with me :-(. I am making any mistake ? Huh, need time to check the code !

Saturday Feb 09, 2008

Sorting with different locale

Sorting is always a tricky game in any language. Language like Java has
its own high class sorting API's. But have you ever think, how sorting
works on different locale ? How it works in French or in Spanish? Lets
have a look...

This is my String Array which I want to sort:
String[] names = {"fácil", "facil", "fast","Où", "êtes-vous", "spécifique", "specific", "ou"};
It contains words of French Locale(some of my fav. words like Où :-) )
And here goes our typical sorting program:

String[] names = {"fácil", "facil", "fast","Où", "êtes-vous", "spécifique", "specific", "ou"};
List list = Arrays.asList(names);
Collections.sort(list);
Iterator itr = list.iterator();
while(itr.hasNext()) {
System.out.print(itr.next()+ " ");
}

And the result:
Où facil fast fácil ou specific spécifique êtes-vous

Result
can surprise you and can make your French friend angry :-) because he
never want "fast" should come before "fácil", just because there is one
special 'á' (sorting is true according to UNICODE sequence but not
according to locale)

To face this problem JDK comes with something called Collator (I guess in 1.4 onwards) which take care of locale while sorting.
Collator is an abstract class. You can look the source code at location in Openjdk: jdk\\src\\share\\classes\\java\\text\\Collator.java. Highly documented file.

Collator
has some flavors like PRIMARY, SECONDARY, TERTIARY, IDENTICAL which all
tells what need to take care while sorting. Please read the javadoc for detail.

Now here is my simple code:

import java.text.\*;
import java.util.\*;


class CollatorTest {

public static void main(String[] args) {
String[] names = {"fácil", "facil", "fast","Où", "êtes-vous", "spécifique", "specific", "ou"};
List list = Arrays.asList(names);
Collections.sort(list);
Iterator itr = list.iterator();
while(itr.hasNext()) {
System.out.print(itr.next()+ " ");
}

Locale[] loc = Collator.getAvailableLocales();

/\* for(int i=0;
i<loc.length;i++)
{
System.out.println(loc[i].getDisplayName());
}
\*/
Collator myCollator = Collator.getInstance(new Locale("fr"));
myCollator.setStrength(Collator.PRIMARY);
Collections.sort(list, myCollator);
itr = list.iterator();
System.out.println("");
while(itr.hasNext()) {
System.out.print(itr.next() + " ");
}

myCollator.setStrength(Collator.TERTIARY);
Collections.sort(list, myCollator);
itr = list.iterator();
System.out.println("");
while(itr.hasNext()) {
System.out.print(itr.next() + " ");
}
}
}

And here is the result:
Où facil fast fácil ou specific spécifique êtes-vous
êtes-vous facil fácil fast Où ou specific spécifique
êtes-vous facil fácil fast ou Où specific spécifique

First
one is the normal sorting, second and third is Collator sorting with 2
different types. You can very easily see that we are giving respect to
other locale as well in sorting. There are 2-3 line comments in the
code, which will tell which all locale Collator is supporting.

About

Hi, I am Vaibhav Choudhary working in Sun. This blog is all about simple concept of Java and JavaFX.

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today