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 !

Comments:

Your microbenchmark includes the time needed to load the Arrays class but not the time needed to load the BubbleSort class. Try adding the following code before measuring the sort performance:

for (int i = 0; i < 10000; i++) {
sortIt(numbers.clone(), length);
sortbyAPI(numbers.clone());
}

Posted by Chris Elving on June 10, 2008 at 08:26 PM IST #

Thanks Chris. Got the point. So, Bubble sorting in a different class so that it will load the class at that time.

Checked it. Its working fine.

Posted by Vaibhav Choudhary on June 11, 2008 at 02:52 AM IST #

Writing good micro benchmarks isn't easy. In order to get meaningful results you've to check a few things. Things you've omitted for example are:
1. Warmup.
2. A test needs to run for at least a few seconds.
3. Don't run tests sequentially. Only one test should be performed per run otherwise it may skew the results (especially with the client VM).

FWIW the results I get (w/o modification) are:
86044 nanoseconds (BubbleSort)
79060 nanoseconds (Arrays.sort)

By the way a nicer way to print arrays is Arrays.toString(int[] a).

Posted by Jos Hirth on June 12, 2008 at 04:03 PM IST #

Post a Comment:
Comments are closed for this entry.
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