In this tutorial, we will learn how to implement Insertion Sort in java. First, we will start by understanding the Insertion Sort algorithm.
Insertion Sort Algorithm
Insertion sort is a simple sorting algorithm that sorts the elements in an array by comparing the values at index with all its prior elements. This process takes more time so it is only used for small data set.
This sorting takes the first index element and compares it to its largest value in an array and it moves the element to its right location.
Before we begin, you need to have an idea of the following:
Time Complexity of Heap Sort:
- Best case:
0(n) - Average case:
0(n^2) - Worst case:
0(n^2)
Implementation of Insertion Sort in java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 | public class InsertionSortJava { public static void insertionSort(int array[]) { int n = array.length; for (int j = 1; j < n; j++) { int key = array[j]; int i = j - 1; while ((i > -1) && (array[i] > key)) { array[i + 1] = array[i]; i--; } array[i + 1] = key; } } public static void main(String a[]) { int[] arr = { 5, 11, 32, 1, 45, 6, 2 }; System.out.println("Array before sorting: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } System.out.println(); insertionSort(arr); //sorting array using insertion sort System.out.println("Array after Insertion Sorting: "); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } } |
The output of Insertion sort algorithm in java:
