Insertion Sort Java Algorithm | JavaSorting

Total Views : 70
Zoom In Zoom Out Read Later Print

we will discuss two different ways to implement Insertion sorting In Java Application. The project download URL has been added so that you can easily execute the given program, with appropriate examples and samples outputs added for Insertion sort In Java.

Here we are using two ways for sorting but they are not different from each other. Only difference is how we get input from the user and store it. Sorting of the element will be done in same way.

We will use following 2 ways to implement Insertion Sort in Java.

1. Using Buffered Reader.
2. Using Array.

Insertion Sort Using Buffered Reader

SortBufferReader.java

package com.manjeet.prodevsblog.insert;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class SortBufferReader {

    public static void main(String[] args) throws IOException {

        System.out.println("Sorting Using Buffered Reader....");

        int n, i;
        BufferedReader b = new BufferedReader(new InputStreamReader(System.in));

        System.out.print("Enter Number of Elements (n):");
        n = Integer.parseInt(b.readLine());
        int[] array = new int[n];

        System.out.println("Enter "+n+" Elements (Press Enter After Each Element) ");

        for( i = 0; i < n; i++) {
            array[i] = Integer.parseInt(b.readLine());
        }

        System.out.println( "Elements in Array Before Sorting...");
        printArray(array);

        sortArray(array);

        System.out.println( "Elements in Array After Sorting");
        printArray(array);
    }

    public static void sortArray(int[] array) {
        int n = array.length, i, j, p, temp;
        for (i = 1;i < n; i++) {

            for (j=i-1; j >=0 && array[j+1] < array[j]; j--) {
                temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
            }
        }
    }

    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + " ");
        }
        System.out.println();
    }
}

Output:

Sorting Using Buffered Reader....
Enter Number of Elements (n):5
Enter 5 Elements (Press Enter After Each Element) 
23
345
567
2
23
Elements in Array Before Sorting...
23 345 567 2 23 
Elements in Array After Sorting
2 23 23 345 567 

Process finished with exit code 0

Insertion Sort Using Array & Scanner

SortArray.java

package com.manjeet.prodevsblog.insert;

import java.util.Scanner;

public class SortArray {

    public static void main(String[] args) {
        
        System.out.println("Sorting Using Array & Scanner....");

        int n, i;
        Scanner s = new Scanner(System.in);

        System.out.print("Enter Number of Elements (n):");
        n = s.nextInt();
        int[] array = new int[n];

        System.out.println("Enter "+n+" Elements (Press Enter After Each Element) ");

        for( i = 0; i < n; i++) {
            array[i] = s.nextInt();
        }

        System.out.println( "Elements in Array Before Sorting...");
        printArray(array);

        sortArray(array);

        System.out.println( "Elements in Array After Sorting");
        printArray(array);
    }

    public static void sortArray(int[] array) {
        int n = array.length, i, j, p, temp;
        for (i = 1;i < n; i++) {

            for (j=i-1; j >=0 && array[j+1] < array[j]; j--) {
                temp = array[j+1];
                array[j+1] = array[j];
                array[j] = temp;
            }
        }
    }

    public static void printArray(int[] array) {
        for (int value : array) {
            System.out.print(value + ", ");
        }
        System.out.println();
    }
}

Output:

Sorting Using Array & Scanner....
Enter Number of Elements (n):5
Enter 5 Elements (Press Enter After Each Element) 
13
7
2
6
10
Elements in Array Before Sorting...
13, 7, 2, 6, 10, 
Elements in Array After Sorting
2, 6, 7, 10, 13, 

Process finished with exit code 0

Sample Recursive Calls :

Elements in Array Before Sorting...
13, 7, 2, 6, 10, 
Loop 1 Array Start----------------
7, 13, 2, 6, 10, 
Array After Loop 1----------------
7, 13, 2, 6, 10, 
Loop 1 Array End----------------
Loop 2 Array Start----------------
7, 2, 13, 6, 10, 
2, 7, 13, 6, 10, 
Array After Loop 2----------------
2, 7, 13, 6, 10, 
Loop 2 Array End----------------
Loop 3 Array Start----------------
2, 7, 6, 13, 10, 
2, 6, 7, 13, 10, 
Array After Loop 3----------------
2, 6, 7, 13, 10, 
Loop 3 Array End----------------
Loop 4 Array Start----------------
2, 6, 7, 10, 13, 
Array After Loop 4----------------
2, 6, 7, 10, 13, 
Loop 4 Array End----------------
Elements in Array After Sorting
2, 6, 7, 10, 13,

1. The numbers enterd by the user will be stored in the Array array[].

2. The function printArray() prints the array elements, function sortArray() will sort the array elements using Insertion sort.

3. The elements in the array are 13, 7, 2, 6, 12.

3.1. For 1st iteration, the inner loop compares the number with the previous number, if the previous number is greater than this number then shift the least number to left.

3.2. For i=1, inner loop compares the numbers 7 < 13, then 7 will be shifted to left. Then the series is 7, 13, 2, 6, 12. In this sorted subarray is 7,13.

3.3. For i=2, the inner loop compares the numbers 2 < 13, shift 2 to left, compare 2 < 7, shift 2 to left. Then the sorted subarray is 2, 7, 13. The series is 2, 7, 13, 6, 12.

3.4.For i=3, the inner loop will compare the numbers 6 < 13, shift 6 to left, compare 6 < 7, shift 6 to left, compare 6,2. The sorted subarray is 2, 6, 7, 13 and the series is 2, 6, 7, 13, 12.

3.5. For i=4, the inner loop will compare the numbers 12 < 13, shift 12 to left. The sorted series is 2, 6, 7, 12, 13.

You can download the Complete project from below link.

See More

Latest Photos