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.
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_arras seen in line 3 in the code above. -
The second step is to create an outer
for loopwhich will iterate over each element of the array as shown in line 5. -
The third step is to create a separate iterator,
jwhich 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
jmust be greater than 0, and the value at indexj-1, must be greater than the value at indexj. - If this condition holds true then, as shown from lines 11 to 14, the
keyis set to the value at indexj. - Then the values at
jandj-1are swapped. - The value of
jis reduced by 1 and the loop continues till one of the conditions breaks.
- As shown in line 9 the while loop must satisfy two conditions: the value of
-
This continues for every iteration of the outer
for looptill 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
