How to implement Insertion Sort in java

Posted on Updated on

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or mergesort. However there are some advantages of insertion sort.

  1. It is very efficient for small data sets.
  2. It does not change the relative order of elements with equal keys.
  3. Requires a constant amount O(1) of additional memory space.

Performance of Insertion Sort.

Worst case performance : О(n2) comparisons
Best case performance : O(n) comparisons
Average case performance : О(n2) comparisons

Understand Insertion sort with an example.Insertion-sort

1st index iteration: Value at position 1 is 5 which is less than value at position 0, So after iteration 1 array becomes [10, 5, 87, 32, 14, 22].

2nd index iteration: Value at position 2 is 87 which is greater than 10, so array remains same after 2nd iteration which is [10, 5, 87, 32, 14, 22].

3rd index iteration: Value at position 3 is 32 which is less than 87, So after iteration 3 array becomes [5, 10, 32, 87, 14, 22].

4th index iteration: Value at position 4 is 14 which is less than 87, so array becomes [5, 10, 32, 14, 87, 22]. Again 14 is less than 32, so array becomes [5, 10, 14, 32, 87, 22]. This time 14 is greater than 10 so after iteration 4 array becomes [5, 10, 14, 32, 87, 22].

5th index iteration: Value at position 5 is 22 which is less than 87, so array becomes [5, 10, 14, 32, 22, 87]. Again 22 is less than 32, so array becomes [5, 10, 14, 22, 32, 87]. This time 22 is greater than 14 so after iteration 5 array becomes [5, 10, 14, 22, 32, 87].

Let us see how this can be implemented in Java.

Output

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.