Insertion Sort

                                                                    Insertion Sort

This is very easy technique to arrange the list of elements either in ascending or descending order.

Insertion sort algorithm arranges a list of elements in a particular order. In insertion sort algorithm, every iteration moves an element from unsorted portion to sorted portion until all the elements are sorted in the list.

The insertion sort algorithm is performed using following steps...

• Step 1: Assume that first element in the list is in sorted portion of the list and remaining all elements are in unsorted portion.
• Step 2: Consider first element from the unsorted list and insert that element into the sorted list in order specified.
• Step 3: Repeat the above process until all the elements from the unsorted list are moved into the sorted list.

Lets see how it works:

Insertion sort start's sorting an array by picking 1st element of array.
(We begin by assuming that a array with one item (position 0) is already sorted.)
So now we have one sorted elements set.

Now, we will pick 2nd element of array and compare it with sorted elements set one by one until we find correct position of 2nd element in sorted set.
Elements which are higher than 2nd element are shifted one step back to make space for 2nd element.
After putting 2nd element at its correct position, we have 2 elements in our sorted set. 

Now, we will pick 3rd element of array and compare it with sorted elements set one by one until we find correct position of 3rd element in sorted set.
Elements which are higher than 3rd element are shifted one step back to make space for 3rd element.
After putting 3rd element at its correct position, we have 3 elements in our sorted set. 

Importants Points

1. The insertion sort, unlike the other sorts, passes through the array only once.
2. The insertion sort splits an array into two sub-arrays,

    First sub-array on left side is always sorted and increases in size as the sort continues.
    Second sub-array is unsorted, contains all the elements yet to be inserted into the first sub-array, 
    and decreases in size as the sort continues.

3. Insertion sort is efficient for (quite) small data sets.
4. It is more efficient than selection sort or bubble sort.
5. Insertion sort is very efficient for arrays which is nearly(almost) sorted and it sorts nearly sorted 
    array in time complexity of O(N).
    (For sorting an array containing elements in descending order to ascending order, insertion sort 
    will give poor performance and complexity will be O(N^2))

6. It is Stable sort; i.e., does not change the relative order of elements with equal keys.
7. It is In-place sort; i.e., only requires a constant amount O(1) of additional memory space
8. It can sort elements as it receives it and no need of complete data initially before start sorting.
    (Online).

Application of Insertion Sort and Where can we use it..

1) If the list of item is not more than 30 or 50 then we can use the insertion sort.

2) Adding elements to a list one at a time over an extended period of time while keeping the list sorted. 

Java Program to demonstrate Insertion Sort

public class InsertionSort {

public static void main(String[] args) {

int list[] = { 15, 20, 10, 30, 50, 18, 5, 45 };

int i = 1;

while (i < list.length) {

int temp = list[i];

int j = i - 1;

while ((j >= 0) && (temp < list[j])) {

int swap = temp;

list[j + 1] = list[j];

list[j] = swap;

j--;

}

i++;

}

System.out.println(Arrays.toString(list));

}

}

Home