Insertion Sort Algorithm in Java and Python

I've started to study more about algorithms. I think that it will be an excellent challenge and great experience.
I found this course in MIT Open CourseWare website :  "Introduction to Algorithms (SMA 5503)", and I'm studying from this resource and also I've bought the related book to this course.

Well, I'm going to post entries related to algorithms in Java, Groovy and Python language (my new lovers :) ).
For Java coding I'm going to create an interface to be implemented for all my algorithm classes.

package melg.algorithms.sorting;

public interface ISorting {

 long[] makeSorting(long[] array, boolean debug);
 
 String getStats();
}

Also I'll use this tool class, in order to be used for debugging purpose:

package melg.algorithms.sorting;


public class SortUtilAlgorithm {

 /**
  * Prints in the console the items of the array object
  * 
  * @param array
  *            the array object.
  */
 public static void showArray(long[] array) {
  System.out.print("[");
  for (int i = 0; i < array.length; i++) {
   System.out.print(array[i]);
   if (i != (array.length - 1)) {
    System.out.print(",");
   } else {
    System.out.println("]");
   }
  }
 }

 /**
  * Generates an array object with long numbers.
  * 
  * @param factorItems
  *            factor for number of items of the array
  * @param factorMaxValue
  *            factor for the maximum value of long numbers
  * @return
  */
 public static long[] genereteArray(int factorItems, long factorMaxValue) {
  Double items = Math.ceil(Math.random() * factorItems);
  long[] array = new long[items.intValue()];
  for (int i = 0; i < items.intValue(); i++) {
   array[i] = (long) Math.ceil(Math.random() * factorMaxValue);
  }
  return array;
 }

 /**
  * Returns a string containing statistics information.
  * 
  * @param rt   running time
  * @param noi   number of iterations
  * @return
  */
 public static String getStats(long rt, long noi) {
  StringBuilder str = new StringBuilder();
  double seconds = rt / (Math.pow(10, 9));
  String strSeconds = String.format("%10.10f", seconds);
  str.append("Time of Execution:\t").append(rt).append(" ns.\n")
    .append("\t\t\t").append(String.valueOf(strSeconds))
    .append(" s.\n").append("Number of Total Iterations:\t")
    .append(noi).append(" times.\n");
  return str.toString();
 }
}

Next, I show the implementation class of the Insertion Sort algorithm.

package melg.algorithms.sorting;

public class InsertionSortAlgorithm implements ISorting {

 private long runningTime = 0;
 private long numberOfIteration = 0;

 /**
  * Implementation of Insertion sort Algorithm
  * 
  * @param array
  *            array object of long values to be sorted.
  * @return the sorted array
  */
 public long[] makeSorting(long[] array, boolean debug) {
  runningTime = System.nanoTime();
  for (int i = 1; i < array.length; i++) {
   long key = array[i];
   int j = i - 1;
   if (debug)
    System.out.println("Inserting:" + key);
   while (j >= 0 && array[j] > key) {
    array[j + 1] = array[j];
    // A[j] = key;
    j--;
    if (debug)
     SortUtilAlgorithm.showArray(array);
    numberOfIteration++;
   }
   array[j + 1] = key;
   if (debug) {
    System.out.println("Inserted:" + key);
    SortUtilAlgorithm.showArray(array);
   }
   numberOfIteration++;
  }
  runningTime = System.nanoTime() - runningTime;
  return array;
 }

 public static void main(String... args) {
  long array[] = SortUtilAlgorithm.genereteArray(10, 200);
  System.out.println("Source array has a size of : " + array.length);
  SortUtilAlgorithm.showArray(array);
  ISorting algorithm = new InsertionSortAlgorithm();
  array = algorithm.makeSorting(array, true);
  SortUtilAlgorithm.showArray(array);
  System.out.println(algorithm.getStats());
 }

 @Override
 public String getStats() {
  return SortUtilAlgorithm.getStats(runningTime, numberOfIteration);
 }
}

Here one output of the running class:

Source array has a size of : 8
[74,142,54,89,76,176,147,92]
Inserting:142
Inserted:142
[74,142,54,89,76,176,147,92]
Inserting:54
[74,142,142,89,76,176,147,92]
[74,74,142,89,76,176,147,92]
Inserted:54
[54,74,142,89,76,176,147,92]
Inserting:89
[54,74,142,142,76,176,147,92]
Inserted:89
[54,74,89,142,76,176,147,92]
Inserting:76
[54,74,89,142,142,176,147,92]
[54,74,89,89,142,176,147,92]
Inserted:76
[54,74,76,89,142,176,147,92]
Inserting:176
Inserted:176
[54,74,76,89,142,176,147,92]
Inserting:147
[54,74,76,89,142,176,176,92]
Inserted:147
[54,74,76,89,142,147,176,92]
Inserting:92
[54,74,76,89,142,147,176,176]
[54,74,76,89,142,147,147,176]
[54,74,76,89,142,142,147,176]
Inserted:92
[54,74,76,89,92,142,147,176]
[54,74,76,89,92,142,147,176]
Time of Execution: 5054274 ns.
   0.0050542740 s.
Number of Total Iterations: 16 times.

Also I like to add the code of this sorting algorithms in Python. Why? Because I love it :). I have started to learn others languages than Java Python and Groovy, and maybe a little Ruby. Next the code for Python language, it was tested with Python 2.7, for python 3.0 there is a issue with conversion from float to integer. In Python 3, they are explicit, and in Python 2.7, you need to do the casting to integer with int() operation.

'''
Created on 15/03/2012

@author: Manuel Loayza
@contact: mloayzagahona at gmail dot com
'''

import math
from random import random 

class InsertionSortAlgorithm:
    def __init__(self):
        pass
            
    '''
    Implementation of the Insertion Sort Algorithm
    '''
    def makeSorting(self, array, debug):
        size = len(array)
        for i in range(1, size):
            key = array[i]
            j = i - 1
            if debug: 
                print("Verifying element: {0}".format(key))
            while (j >= 0 and key < array[j]) :
                array[j + 1] = array[j]
                j -= 1
                if debug :
                    self.showArray(myarray)
            array[j + 1] = key
            if debug: 
                print("Element Inserted: {0}".format(key))
                self.showArray(myarray)
    
    '''
    Shows the array in the console
    '''
    def showArray(self, array):
        size = len(array)
        string = "["
        for i in range(0, size):
            string = string + "%s" % array[i]
            if i != (size - 1) :
                string = string + ","
            else:
                string = string + "]"
        print(string)
        
if __name__ == "__main__":
    sorting = InsertionSortAlgorithm()
    myarray = []
    items = int(math.floor(random() * 20))
    for i in range (0, items):
        myarray.append(int(math.floor(random() * 200)))    
    print("The source array has a size of : {0}".format(items)) 
    sorting.showArray(myarray)
    sorting.makeSorting(myarray, True)
    print("The target sorted array")
    sorting.showArray(myarray)

Here one execution of this python code.

The source array has a size of : 5
[13,33,27,13,4]
Verifying element: 33
Element Inserted: 33
[13,33,27,13,4]
Verifying element: 27
[13,33,33,13,4]
Element Inserted: 27
[13,27,33,13,4]
Verifying element: 13
[13,27,33,33,4]
[13,27,27,33,4]
Element Inserted: 13
[13,13,27,33,4]
Verifying element: 4
[13,13,27,33,33]
[13,13,27,27,33]
[13,13,13,27,33]
[13,13,13,27,33]
Element Inserted: 4
[4,13,13,27,33]
The target sorted array
[4,13,13,27,33]

Finally, the code of this algorithm in Groovy.

package melg.algorithms.sorting


class InsertionSortAlgorithm {

 private boolean debug = false
 /*
  * Implementation of the Insertion Sort Algorithm
  */
 public void makeSorting(array){
  int items = array.size()
  for (i in 1..< items){
   long key = (long)array[i]
   int j = i - 1
   if (debug) println "The value ${key} is being verified."
   while (j >= 0 && key < array[j]) {
    array[j+1] = array[j]
    j = j - 1
    if (debug)showArray(array)
   }
   array[j+1] = key
   if (debug) {
    println "The value ${key} was inserted."
    showArray(array)
   }
  }
 }

 def void setDebug(value){
  this.debug = value
 }

 public static void showArray(array){
  print "["
  int size = array.size(), count = 0;
  array.each{
   print it
   if (size > (count + 1)){
    print ","
   }
   count++
  }
  println "]"
 }
}

def array = []
float size = Math.ceil(Math.random() * 3500 )
for (i in 0..< size.toInteger()){
 array << Math.ceil(Math.random() * 65000 ).toInteger()
}

InsertionSortAlgorithm insertion = new InsertionSortAlgorithm();
println "The source array has ${array.size()} items."
InsertionSortAlgorithm.showArray(array);
insertion.makeSorting(array);
println "\nThe target sorted array is:."
InsertionSortAlgorithm.showArray(array);

It is the result of my first try with sorting algorithms, maybe later I'm going to add some theory and maths about this kind of algorithm.

Good luck.