Insertion Sort Program in Java. Write a java program to sort an unsorted array using insertion sort.
In this tutorial, We are going to cover following points.
- How insertion sort works?
- Insertion sort program in java.
- Video tutorial which explain insertion sort algorithm.
Let’s say we have an unsorted array and we want to sort this array using insertion sort. Let’s first understand how insertion sort works?
Input : {5, 4, 2, 9, 1}
Output : {1, 2, 4, 5, 9}
How insertion sort works?
i) Traverse an array from left to right.
ii) Take each items of an array and compare it to items on it’s left.
iii) Insert it to it’s correct position.
The time complexity of insertion sort is O(n^2).
Insertion Sort
Insertion Sort Program in Java
We have discussed insertion sort algorithm and how this algorithm sort an unsorted array. Let’s write a java code which implements insertion sort algorithm.
Sorting algorithms and their time complexities
|
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 40 41 42 |
/* Java Program to Implement insertion sort */ public class InsertionSort { public static void insertionSort(int arr[]) { int temp; int j; //Traverse an array from left to right for(int i = 1; i < arr.length; i++) { temp = arr[i]; j = i- 1; while(j >= 0 && temp < arr[j] ) { arr[j+1] = arr[j]; j = j-1; } arr[j+1] = temp; } } public static void main(String[] args) { int arr[] = {5, 4, 2, 9, 1}; //sort an array insertionSort(arr); //Print the sorted array for(int k = 0; k < arr.length; k++) { System.out.print( arr[k] + " "); } } } |
Insertion Sort Video Tutorial
In this video tutorial, I have explained how insertion sort works and it’s implementation using c and java code.
