Implementing Insertion Sort Algorithm in Java Program

Insertion sort is a simple sorting algorithm in which we insert the elements from an unsorted array into a sorted subarray until the entire array is sorted. It's also called a in-place algorithm as it only requires a constant amount of additional memory.

To implement Insertion sort in Java, you can use a for loop to iterate over the unsorted array and an inner while loop to insert the current element into the correct position in the sorted subarray.

package org.code2care.java.sorting.algo;

import java.util.Arrays;

public class InsertionSortJavaExample {

    public static void main(String[] args) {

        //Unsorted Array
        int[] unsortedArray = {4, 99, 2, 11, 34, 67, 54, 12, 45, 245, 234, 12, 200};
        InsertionSortJavaExample insertionSort = new InsertionSortJavaExample();

        int[] sortedArray = insertionSort.insertionSortAlgorithm(unsortedArray);

        System.out.println(Arrays.toString(sortedArray));
    }

    public int[] insertionSortAlgorithm(int[] arrayOfNumbers) {

        int arrayLength = arrayOfNumbers.length;

        for (int i = 1; i < arrayLength; i++) {
            int key = arrayOfNumbers[i];
            int j = i - 1;
            while (j >= 0 && arrayOfNumbers[j] > key) {
                arrayOfNumbers[j + 1] = arrayOfNumbers[j];
                j--;
            }
            arrayOfNumbers[j + 1] = key;
        }

        return arrayOfNumbers;
    }
}

Output:

[2, 4, 11, 12, 12, 34, 45, 54, 67, 99, 200, 234, 245]

	Time Complexity
	Best Case	Average Case	Worst Case	Space Complexity
Selection Sort	O(n)	O(n^2)	O(n^2)	O(1)

Note: Unlike Bubble Sort, Insertion Sort has a lower constant factor in its time complexity, thus it is faster than Bubble Sort for small to medium-sized arrays. You should avoid using Insersion sort for larger datasets and make use of other efficient algorithms like Merge sort and Quick sort.

Have Questions? Post them here!

More Posts related to Java,

More Posts: