Sorting

Insertion sort

Pinterest LinkedIn Tumblr

Insertion sort is a simple sorting algorithm that builds sorted array one item at a time. It is efficient for the small data set.

Insertion sort is best suitable for nearly sorted arrays and the small set of elements. It is similar to selection sort. The selection sort must scan all the elements to find the smallest element. But the insertion sort scans only the remaining elements in the array. The insertion sort can combine with divide and conquer based algorithm for better optimization.

Write a program to implement the insertion sort.

source Code

package com.dsacode.Algorithm.sorting;
 
import java.util.Arrays;
 
public class InsertionSort {
 
    private static void insertionSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            int valueToSort = arr[i];
            int j = i;
            while (j > 0 && arr[j - 1] > valueToSort) {
                arr[j] = arr[j - 1];
                j--;
            }
            arr[j] = valueToSort;
        }
    }
  
    
    public static void populateArray(int[] B) {
        for (int i = 0; i < B.length; i++) {
            B[i] = (int) (Math.random() * 100);
        }
    }
     
     public static void main(String[] args) {
         
            int[] arr={12,34,56,23,45,78,46};
            System.out.println("unsorted array before sorting : " + Arrays.toString(arr));
            insertionSort(arr);
            System.out.println("Sorted array After InsertionSort sorting : " + Arrays.toString(arr));
             
        }
      
}

Output

Unsorted array before sorting: [12, 34, 56, 23, 45, 78, 46]
Sorted array After Insertion Sort sorting: [12, 23, 34, 45, 46, 56, 78]

Algorithm Explanation

Take unsorted array and divide the array into two parts. sorted array and unsorted array.
Take every element from the unsorted array and add to sorted array.
Arrange the elements when adding into sorted array.
When unsorted array becomes empty, the sorted array contains all the elements with sorted.

Time Complexity

Best CaseAverage CaseWorst Case
O(n)O(n^2)O(n^2)

Reference

  1. http://www.ee.ryerson.ca/~courses/coe428/sorting/insertionsort.html
  2. http://cs.armstrong.edu/liang/animation/web/InsertionSort.html
  3. http://en.wikipedia.org/wiki/Insertion_sort

Write A Comment