Saturday, July 19, 2014

Insertion Sort Algorithm using Java

Insertion Sort is simple sort algorithm. In insertion sort, we pickup element and find correct place of element where it needs to be inserted and insert that element at correct place by moving elements to right side.We will keep doing same until we have all sorted elements available on left side.



Java Program using Insert Sort Algorithm :
package com.anuj.algorithms;

import java.util.Arrays;

/**
 *
 * @author Anuj
 * @source goldenpackagebyanuj.blogspot.com
 */
public class InsertionSort {

    public static void main(String[] args) {
        int arr[] = {12, 9, 4, 99, 120, 1, 3, 10};

        System.out.println("Before Sorting :" + Arrays.toString(arr));
        insertionSort(arr);
        System.out.println("After Sorting : " + Arrays.toString(arr));
    }

    public static void insertionSort(int arr[]) {
        System.out.println("Intermediate Happenings : ");
        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;
            System.out.println(Arrays.toString(arr));
        }
    }
}

Output:
run:
Before Sorting :[12, 9, 4, 99, 120, 1, 3, 10]
Intermediate Happenings : 
[9, 12, 4, 99, 120, 1, 3, 10]
[4, 9, 12, 99, 120, 1, 3, 10]
[4, 9, 12, 99, 120, 1, 3, 10]
[4, 9, 12, 99, 120, 1, 3, 10]
[1, 4, 9, 12, 99, 120, 3, 10]
[1, 3, 4, 9, 12, 99, 120, 10]
[1, 3, 4, 9, 10, 12, 99, 120]
After Sorting : [1, 3, 4, 9, 10, 12, 99, 120]
BUILD SUCCESSFUL (total time: 0 seconds)

Author : Anuj Patel
Blog : http://goldenpackagebyanuj.blogspot.in/