a shot of dev knowledge

RELATED TAGS

# What is insertion sort in Java?

Insertion sort is a simple sorting algorithm that allows for efficient, in-place sorting of the array, one element at a time. By in-place sorting, we mean that the original array is modified and no temporary structures are needed.

We will learn how to implement this style of sorting in Java.

## Visualizing the sorting

Now that you remember how Insertion sort works, let’s see a small illustration on Insertion sort and how it works on a given array.

The iteration starts at the index = 1, and checks all values on the left side of the key
1 of 11

## Implementation

Now that we have seen how insertion sort works let’s use the example above and write a code that performs this sort.

Change the values of arr to see how it works on different arrays.

class insertionSort {

public static void sortInsertion(int [] sort_arr){

for(int i=0;i<sort_arr.length;++i){

int j = i;

while(j > 0 && sort_arr[j-1]>sort_arr[j]){

int key = sort_arr[j];
sort_arr[j] = sort_arr[j-1];
sort_arr[j-1] = key;
j = j-1;

}
}
}

public static void main( String args[] ) {
int [] arr = {5,2,12,12,1};
sortInsertion(arr);

for(int i=0;i<arr.length;++i){
System.out.print(arr[i] + " ");
}
}
}

## Understanding Implementation

• The first step is to create a method that takes in input the array to be sorted, sort_arr as seen in line 3 in the code above.

• The second step is to create an outer for loop which will iterate over each element of the array as shown in line 5.

• The third step is to create a separate iterator, j which will check for the ascending order of elements in the list, as shown in line 7.

• The fourth step is the inner while loop:

• As shown in line 9 the while loop must satisfy two conditions: the value of j must be greater than 0, and the value at index j-1, must be greater than the value at index j.
• If this condition holds true then, as shown from lines 11 to 14, the key is set to the value at index j.
• Then the values at j and j-1 are swapped.
• The value of j is reduced by 1 and the loop continues till one of the conditions breaks.
• This continues for every iteration of the outer for loop till that also breaks.

### Time Complexity

As there are two loops, with the while loop nested in the for loop the complexity of this algorithm is O(n^2) where n is equal to the length of the array to be sorted.

RELATED TAGS

RELATED COURSES

View all Courses

Keep Exploring

Learn in-demand tech skills in half the time