Blog Image

Insertion Sort  

In this blog,  i am explaining about the Insertion Sort what is insertion sort and how we can swap the elements in proper order using insertion sort.When we can use this sorting mechanism is explained as a part of the blog.

Insertion Sort
Sorting is the process of arranging a list of elements in a particular order (Ascending or Descending).
This algorithm arranges a list of elements in a particular order. Every iteration moves an element from unsorted portion to sorted portion until all the elements are in sorted the list.
How the insertion sorting will happen:
To start the sorting first we assuming that first element is already sorted in the list, after that we can pick the next element in the list and put in the second place, again we compare this element with the first element in the list, if the elements are not sorted in the list then we can swap the elements and we can insert properly. Now again we pick the third element from the list and insert into the third place and compare it with the second position number, if these elements sorting order is not proper we again swap, if all the three elements are still not in sorted order then we again swap the 1st and 2nd elements , then we will get the sorted list of elements .
This is how insertion sort will happen i.e. you take the element from the array list, compare with already sorted elements once and move them forward if it is greater than a current element until you find the right place for your current element.
see below example how insertion sorting will happen,



First, pick the 15 element and move that element to sorted position or first position in the list.
Pick one more element 40 and compare with 15 proper order only.Then we pick one more element 20 we compare with element 40, 20 is smaller than 40 so 20 is inserted in a position of 40.Now we have 3 sorted elements.
We pick on more element 25 compare with the before element 40 and is smaller, So 25 is inserted in the position of 40 and again we compare with remaining elements in the sorted list, 25 is greater then sorted elements so there is no shifting at this time.
We pick next element 30 we compare with 40 and it is smaller, then inserting that 30 element in the position of 40, again compare the remaining elements in the sorted list with the current comparing element if it is smaller then shift that element to correct position otherwise don't move that element.
These process will continue to the remaining elements 18,5 and 42 then we can get the sorted list elements.how we can do this programmatically see below example,
 


package com.sjblog.sort;
public class InsertionSort {
    public static void main(String[] args) {
        int[] input = { 15,40,20,30,25,18,5,42 };
        elementSort(input);
    }
    private static void printNumbers(int[] input) {
        for (int i = 0; i < input.length; i++) {
            System.out.print(input[i] + ", ");
        }
        System.out.println("\n");
    }
    public static void elementSort(int array[]) {
        int n = array.length;
        for (int j = 1; j < n; j++) {
            int key = array[j];
            int i = j-1;
            while ( (i > -1) && ( array [i] > key ) ) {
                array [i+1] = array [i];
                i--;
            }
            array[i+1] = key;
            printNumbers(array);
        }
    }
}


The advantage of the insertion sort is its simplicity.Performance wise it is good when we are dealing with the small list.
If the length of our sorted list increased, so the number of comparison and swapping will be increased, so this sorting algorithm is not suitable for larger dataset.
Disadvantages are when comparing with the other sorting it is does not perform well and insertion sort does not deal with a huge list.

You can download the above maven example from the attachments given below

About author

User Image
sagarreddy

Seeking a challenging position, where I will be a valuable team member, contributing quality ideas and work for an organization where there is an ample scope to grow for an individual as well as organization growth in Software Development.

0

-Comments

Be the first person to write a comment for this Blog
Load More

No More Comments

Leave a Comment

Your comment has been posted and will appear soon.