Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

insertion sort
java
sorting

What is insertion sort in Java?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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.

Note: Need to review of the algorithm? click here.

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

insertion sort
java
sorting
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring