Insertion Sort Algorithm in Java

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time. It’s much less efficient on large list.

1. Get a hand of unsorted card.
2. We divide the card as sorted and unsorted by placing a marker after the first card.
3. Repeat steps 4 to 6 until unsorted section is empty
4. Select the first unsorted card.
5. Swap this card to left until it arrives at the correct sorted position.
6. Advance the marker to the right one 

Let take a deck of unsorted card (step 1).

7 8 5 2 4 6 3
Now we divide this into two portion one is sorted and another is unsorted (step 2).

7|8 5 2 4 6 3

Here we select the first unsorted card i.e., 8 (step 4). Since 8 is greater than 7 so we do not need to swap the card (step 5).

Advance the marker to the right (step 6)

7 8|5 2 4 6 3

Now we select the next unsorted card i.e. 5. Since 5 is less than 8, so we swap the card

7 5|8 2 4 6 3

Since 5 is still less than 7 we swap again until it is corrected sorted position.

5 7|8 2 4 6 3

Advance the marker.

5 7 8|2 4 6 3

Now we put 2 in the right position.

5 7 2|8 4 6 3

5 2 7|8 4 6 3

2 5 7|8 4 6 3

Advance the marker

2 5 7 8 |4 6 3

Now we put 4 in the right position.

2 5 7 4 |8 6 3

2 5 4 7 |8 6 3

2 4 5 7 |8 6 3

Advance the marker

2 4 5 7 8|6 3

Now we put 6 in the right position.

2 4 5 7 6|8 3

2 4 5 6 7|8 3

Advance the marker

2 4 5 6 7 8|3

Now we put 3 in the right position.

2 4 5 6 7 3|8

2 4 5 6 3 7|8

2 4 5 3 6 7|8

2 4 3 5 6 7|8

2 3 4 5 6 7|8

Advance the marker

2 3 4 5 6 7 8|Here is out sorted output.

Demo : 6 5 3 1 8 7 2 4 

Improved Version : If element are already sorted to its left means no swap is required then we can simply comes out of the loop.

Performance :

• Worst Case Complexity : O(n^2) The simplest worst case input is an array sorted in reverse order. In these cases every iteration of the inner loop will scan and shift the entire sorted subsection of the array before inserting the next element
• Average Case Complexity : O(n^2) that why which makes insertion sort impractical for sorting large arrays.
• Best Case Complexity : O(n) When is array is already sorted. During each iteration, the first remaining element of the input is only compared with the right-most element of the sorted subsection of the array.

Q. For insertion sort, the number of entries we must index through when there are n elements in the array is
Ans : n-1


If you know anyone who has started learning Java, why not help them out! Just share this post with them. 
Thanks for studying today!...