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 !

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