Writing an Insertion Sorting Program in Java

This morning I have just woken up after dreaming of a job interview where I was asked to code an insertion sorting program in Java. I know this might probably sounds a bit crazy, but sometimes your dreams do resemble real-life situations, in particularly work-related ones. Anyway, this made me think of the difference between the Bubble and the Insertion sorting algorithm. While the Bubble sorting algorithm (also called sinking sort) repetitively compares each pair of adjacent elements and swaps them if in the wrong order, the Insertion sorting inserts element into the correct position one at the time by making incremental adjusting to the previously list.

Here is a basic Java implementation of the insertion sort algorithm:


import java.util.Arrays;

public class InsertionSort
{

 public static void main (String[] args)
 {
    //initialise an Array of 10 int elements
    int[] myIntArray = new int[10];;
    populateArray(myIntArray); // it populates the Array, although it is not sorted yet
    insertionSort(myIntArray); // Here is where the insertion sort algorithm is applied 
    printArray(myIntArray); // It prints the sorted Array
 } 

 private static void insertionSort(int[] arrayElements) 
 {
    int i; //outer loop starting from [1], that is the second element, 
          //to the end of the list. We assume that all elements to the left of the first 
          //element of the list [0] are smaller than element [0]
    int j; //our inner loop
    int key; //our current element to compare
    int temp; // temp value for swapping elements in the list
 
    for (i = 1; i < arrayElements.length; i++) //It starts at [1] because element [0] is already sorted
    {
       key = arrayElements[i]; // the current element starts with [1]
       j = i - 1; // element of [i] left for comparison with the current element key
       while (j >= 0 && key < arrayElements[j]) //it evaluates if j is less or equal to zero and if there are elements left to be compare with the key
       {
          temp = arrayElements[j];
          arrayElements[j] = arrayElements[j + 1];
          arrayElements[j + 1] = temp;
          j--;
       }
     }
  }
 
 public static void populateArray(int[] populatedArray) 
 {
     for (int i = 0; i < populatedArray.length; i++) 
     {
        populatedArray[i] = (int) (Math.random() * 100);
     }
 }
 
 public static void printArray(int[] sortedArray) 
 {
     for(int i = 0; i < sortedArray.length; i ++ );
     {
        System.out.println(Arrays.toString(sortedArray));
     }
  }
}

 

Advertisements

Posted on October 4, 2015, in Uncategorized. Bookmark the permalink. Leave a comment.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: