Correct Implementation of Insertion Sort

Given a task of implementing insertion sort, many people end up with following code 

    
void insertionSort(int a[]){
 for (int i = 0; i < a.length; i++) {
                
                for (int j = i; j > 0; j--) {
                    int k = j-1;
                        if( a[j] < a[k]){
                            int temp = a[j];
                            a[j] = a[k];
                            a[k] = temp;
                        }
                    
                }
 }
}

Although the code works as expected & sorts the given data in O(n^2) time, but this is the wrong implementation of insertion sort.

Do You Know Why ?

The reason is best case time complexity of insertion sort is O(n) but this code has O(n^2), in short no matter what sequence of data you through at this code it will take O(n^2) time i.e best, avg. & worst case time complexity of this code is O(n^2).

Note: If you have clear your "Analysis of Algorithms & Design" paper you will understand what is written above.

If you have understand the above statements than you can fix the wrong implementation on your own, the above implementation can be corrected by just adding one statement which i left it for you as an exercise.

In case you are in hurry you can adopt My way to write insertion sort

Correct Implementation 

    
 int[] insertionSort(int [] a ){
        for (int j = 1; j < a.length; j++) {
            int i = j-1;
            while ( ( i >= 0 ) && a[i] > a[i+1] ) {                
                int k = a[i];
                a[i] = a[i+1];
                a[i+1] = k;
                i -= 1;
            }
        }
        return a;
    }

The best case time complexity(i.e when array elements are already in ascending order) of this code is O(n) & worst case time complexity is O(n^2), which proves that this code is correct implementation of Insertion Sort.

Swapping Using 2 Variables

Some of mine friends asked me a question, the Question was

Agreed that we can swap two numbers using some math, but how can we swap two chars & string without using 3rd variable ?

This blog post will answer the question, the method i have used is preety simple & straight forward
We will do following swapping

• Number Swapping
• Chars Swapping 
• Strings Swapping

To begin with lets quickly see the codes

• Number Swapping

 void swappingNumbers( int a, int b ){

        System.out.println( "input value  a = " + a + "  b = " + b );
        a = a+b;
        b = a-b;
        a = a-b;
        System.out.println( "swapped values a = " + a + " " + " b = " + b );
    }

The above code swaps two ( signed & unsigned ) numbers without using any 3rd variable

• Chars Swapping 

 void swappingChars(char a, char b ){
        System.out.println( "input value  a = " + a + "  b = " + b );
        int p = (int)a ,q = (int)b;
        p =  ( ( (int) p ) + ((int)q) ) ;
        q = ( ( (int) p ) - ((int)q) ) ;
        p = ( ( (int) p ) - ((int)q) ) ;
        System.out.println( "swapped values p = " +  ( (char)p) + " q = " + ((char)q) );
    }

The above code swaps 2 chars without using 3rd variable. Here using two variable i.e p & q we have swap the chars

• String Swapping

 
void swappingStrings(String str1, String str2){
        System.out.println( "input value  str1 = " + str1 + "  str2  = " + str2 );
        str2 = str1 + " " + str2;
        String[] split = str2.split(" ");
        str1 = split[1];
        str2 = split[0];
        System.out.println( "swapped values = str1 = " + str1 + " str2 = " + str2);
    }

The above code swaps 2 Strings without using 3rd variable.

Output

Hope this helps.

Java Matrix Multiplication (JMM)

Often in many areas of programming people require a tool which can simplify there n*n matrix multiplication problem in reasonable amount of time.

This can usually be done with 3 tight for loop and special care for handling dimension errors(which i assumes most of you knows) to do this i have a designed a special class and added it to my Utilities framework 1.1.2

Lets quickly take 1 example for 2*2 matrix multiplication using Utilities-1.1.2

  

class MatrixMultiplication
{
public static void main(String[] str) throws DimensionError{
        double[][] a = { {1.2,2.25}, {25.0,28.2} };
        double[][] b = { {1.2,2.25}, {25.0,25.2} };
        double[][] multiplyMatrix = new Math().multiplyMatrix(a, b);
        for (double[] ds : multiplyMatrix) {
            for (double d : ds) {
                System.out.print( d + " ");
            }
            System.out.println();
        }
    }
}
}

Output

So, now you know how simple is matrix multiplication.

Dimension Errors

A special care has been taken to indicate that matrix multiplication is not possible and this is indicated using DimensionError Exception

consider the following example

import math.DimensionError;
import math.Math;
public class MatrixMultiplication {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] str) {
        double[][] a = { {1.2,2.25,2}, {25.0,28.2,2}, {25.2, 14.25,2} };
        double[][] b = { {1.2,2.25}, {25.0,25.2} };
 try{
        double[][] multiplyMatrix = new Math().multiplyMatrix(a, b);
        for (double[] ds : multiplyMatrix) {
            for (double d : ds) {
                System.out.print( d + " ");
            }
            System.out.println();
        }
 }catch(DimensionError ex){
  System.out.println(ex.getErrorMessage());
 }
    }
}

Output

Speed

Worst case time complexity is O(n^3)


Download