Sorting and OpenJDK

Wednesday Nov 25, 2009

If you are looking for sorting algorithms and if you use some sorting algorithm in your code/application/big application, then have a look here. First of all sorting/searching is a classic thing. It take more than 70 percent of your application time.People/Developer/Mathematician do a lot of work on optimizing this work to get Best, best out of best.

Early days, JDK used to use QuickSort which is one of the best sorting algorithm and go for a complexity of O(nlogn). But mind it, QuickSort is a recursive algorithm and consume space. Whereas some of the algorithm which has the complexity like O(n^2) go for less complex in terms of memory. These days our platform varies from small mobile device to a terabyte storage machine............

Like this post? | | | |

Posted at 10:11PM Nov 25, 2009 by vaibhavc in Java
Tags: java openjdk sort

Avoid Array Sorting API for small list ?

Wednesday Jun 11, 2008

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 !

Like this post? | | | |

Posted at 12:16AM Jun 11, 2008 by vaibhavc in Java
Tags: arrays bubble code comparsion java openjdk sort sorting