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.

-

Have Questions? Post them here!