Sunday, December 28, 2008

Insertion sort in Java using generics

Insertion sort
It looks at the next item of the input and inserts it into its correct position in the "already sorted" previous items of the input. Here is the code for it using Java Generics.

public class MyInsertionSort {

public <T extends Comparable<T>> void doInsertionSort(T[] input) {

if (input == null) {
throw new RuntimeException("Input array cannot be null");
}
int length = input.length;
//Already sorted
if (length == 1) return;
int i,j;
T temp;
for (i = 1; i < length; i++) {
//Store the current element
temp = input[i];
//Compare the current element with
//the partially sorted group
//to see if its in the correct position
for (j = i; (j > 0 && (temp.compareTo(input[j-1]) < 0)); j--){
//The current element is not in
// its correct position in the
//partially sorted list. Move
//the larger item one place
//to right and make space
// for the current element
input[j] = input[j-1];
}
//Found the correct position
//for the current element
//in the partially sorted group.
//So move it to its correct place.
input[j] = temp;
}

}


Test it.



public class MyMain {

public static <T> void printArray(T[] input) {
for(T elem: input) {
System.out.print(elem);
System.out.print(" ");
}
System.out.println();
}

public static void main(String[] args) {

String[] s = {"Hello", "World", "Hello"};
Integer[] intArray = {1,4,9,0,8,7,9,6};

//Test insertionsort
MyInsertionSort is = new MyInsertionSort();
is.doInsertionSort(s);
is.doInsertionSort(intArray);
printArray(s);
printArray(intArray);


}

}


Running it produces the following output:
Hello Hello World
0 1 4 6 7 8 9 9

Efficiency of Insertion sort
In the first pass we will have max of 1 comparision,in the second one we will have a max of 2 comparisions and so on. So this is
1+2+3+....(n-1) and it sums up to roughly n(n-1)/2 i.e. approximately n². So the running time for random data it is O(n²) but for already sorted data it will never enter the second for loop, so it will run in O(n) .

Analysis
The insertion sort is not a good sort for large inputs of data. More information on Insertion sort can be found here.

Tuesday, December 23, 2008

Formatting code for blogging

I have been using java2html to format code in blogs. Its very easy to install and use it. Recently I found another website which has an application to format source code. I tried it and it seems better at formatting for blogger (maybe other blogs too, I haven't tried). I will probably switch to using this in the future.

Saturday, December 20, 2008

Auto unboxing pitfall

Lets try a simple code snippet to see how unboxing of null works.


public class TestAutoBoxingUnboxing {
     public static void main(String[] args) {
         Integer a = null, b = null;
         int iAmA = a;
         int iAmB = b;

         //Will this print???
         System.out.println("Lets see the primitive ints " + iAmA + " and " + iAmB);
     }
}


Running the code produces:
Exception in thread "main" java.lang.NullPointerException at TestAutoBoxingUnboxing.main(TestAutoBoxingUnboxing.java:17)


Moral:

Cannot unbox null, it will throw a NullPointerException. So we have to be more careful with primitives than before to avoid such problems.

Saturday, December 13, 2008

My favorite Java books

Listed below are some of the Java books I enjoyed reading.

Effective Java by Joshua Bloch
I have read the first edition. It is an excellent book on best practices. It is meant for intermediate to advanced programmers. I had to read some chapters more than once to grasp the concepts. Save it for serious reading.

SCJP 5 by Kathy Sierra and Bert Bates
It is recommended as a must have book for certification. I personally used it to review my Java skills. I absolutely loved the book, its very easy to follow. If you are trying to learn the Java language read another book first.

Core Java Vol I by Cay Horstman
This book keeps growing in size with every edition. The sheer size could scare people, however, it is a very good book for learning Java. It covers Java 6 features too. A note of caution though, if you are new to programming, this not the right book for you.

Head First Java by Kathy Sierra and Bert Bates
I became a great fan of Kathy and Bert after reading SCJP 5 and decided to read this one eventhough I am not new to Java. I borrowed it from the library which only had the first edition. It is a very good book to learn Java language even for ones without programming background. One needs to get used to the new style of teaching. You may either like the approach or not. I personally enjoyed reading it.

Professional Java Puzzlers by Josh Bloch.
Fun, Fun, Fun. Once I started reading I wasnt able to stop. It exposes pitfalls and oddities of the language. If you have the time then borrow it and read it.

Practical Java by Peter Haggar
Another book on some good programming practices. I really really enjoyed reading it. It is easy to read, very clear and concise. I think even beginners can understand some essays(Praxis). Advanced programmers may prefer Effective Java.

Algorithms in Java by Sedgewick
I havent finished reading it because many sections require re-reading, it is very dense and meant to be read with least amount of distractions. I like the book so far because it covers the fundamentals of algorithms very well and has some really good examples. The only gripe I have so far is that no answers are provided to the exercises.

Head First Servlets and JSP by Basham, Siera and Bates
I havent finished reading it fully but I have liked what I have read. Though it says it is geared towards SCWCD, it is a very good book even for beginners, its easy to understand but one needs to know some Java.