Implementing Insertion Sort Algorithm in Java Program


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 CaseAverage CaseWorst CaseSpace Complexity
Selection SortO(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.

Facing issues? Have Questions? Post them here! I am happy to answer!

Author Info:

Rakesh (He/Him) has over 14+ years of experience in Web and Application development. He is the author of insightful How-To articles for Code2care.

Follow him on: X

You can also reach out to him via e-mail: rakesh@code2care.org

Copyright © Code2care 2024 | Privacy Policy | About Us | Contact Us | Sitemap