Introduction

Insertion Sort is part of one of the sorting techniques in JAVA. This is a simplistic method to sort elements (generally in ascending or descending order) in an array (or other data structures). Insertion sort breaks up an array into two sections. As it is a dynamic process and occurs when inside a loop, until the last element of the array is sorted, one part of the array remains sorted and the other part remains unsorted.

Algorithm

The Insertion Sort logic or algorithm is a two-stepped process. The iteration runs from the 2^nd element of the array (arr[1]) until the length of the array. As it is a two-staged process, there are nested loops at play.

• The outer loop checks if the [n+1] element of the array is smaller than the [nth] element of the array. If the condition is satisfied, the program goes into the next loop.
• This loop compares the current element (key) to the elements before it and keeps in swapping until an ascending order of values is achieved.

Code with Example

class InsertionSort{
void InsSort(int arr[])
{
int n = arr.length;
for (int i = 1; i<n;i++) {
int flag = arr[i];
int j = i– 1;
//Now swapping elements
while(j>=0 && arr[j] > flag) {
arr[j+1] = arr [j];
j = j – 1;
}
arr[j + 1] = flag;
}
//To print out the array in ascending (or descending order if required)
public static printArr(int arr[])
{
int len = arr.length;
for (int i = 0; i<n ; i++)
System.out.println (arr[i] + “ ”);
//This print statement will print out a blank line
System.out.println ();
}
public static void main (String args [])
{
int arr[] = { 1 , 6, 7, 2, 34, 90, 44, 73, 0};
InsertionSort obj = new InsertionSort();
obj.InsSort(arr);
printArr(arr);
}
}

OUTPUT

0
1
2
6
7
34
44
73
90