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.

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

RELATED COURSES

View all Courses

Keep Exploring