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.
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.
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] + " ");}}}
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
:
j
must be greater than 0, and the value at index j-1
, must be greater than the value at index j
.key
is set to the value at index j
.j
and j-1
are swapped.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.
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
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.