insertion sort algorithm in java

Insertion sort algorithm in java

The insertion sort algorithm focuses on a single element of the list and tries to find the correct location for that element. When searching for the correct position, only positions below the current position are considered. Thus, on the first pass, the first element is always in the correct position so it is redundant to perform this step.

 

Example:

consider an example of following array:

Pass 1: 

• compare 3 to all values to the left of it; if they are larger, shift them right
• 6 is larger than 3, so move 6 to position 1
• put 3 in the empty location

 

Pass 2:

• compare all values to 5
•  5 is less than 6, so shift 6 right to position 2
•  5 is greater than 3, so stop; put 5 in position 1

 

pass 3:

• no change; 8 is already in the correct location

 

pass 4:

• compare all values to 2
• 2 is less than each value below it, so they will be shifted right by one after each comparison
• when the bottom of the list is reached, the pass ends, and 2 is put at the available location at the beginning

 

Java implementation for insertion sort:

For each pass, we need to copy the element under consideration into a temporary location. Now, as we move from right to left through the array, we shift any larger values to the right. Once we have moved any larger values, we put our target element into the last empty location.

Performance of insertion sort algorithm:

• Best case is obviously when array is already in sorted order. The inner loop of algorithm  is never executed. so the best case is O(N).
• Worst case: the inner loop is executed exactly j − 1 times for every iteration of the outer loop.
  • The worst-case complexity is Θ(n 2 ). • The worst-case inputs A consist of distinct items in reverse sorted order:
  • a[0] > a[1] > . . . > a[n − 1]. • The total worst-case number of comparisons is 1 + 2 + . . . + n − 1 = (n−1)n 2 = 1 2 (n 2 − n) ∈ Θ(n 2 ).
• Insertion sort takes N(N-1)/2=N2/2-N/2 comparisons . N/2 grows much slower than N2/2, so we can toss that The constant 1/2 is affected by the details of a machine, which are not essential either. We are left only with N2. We say the complexity of insertion sort is O(N2)

Let’s see whether insertion sort is stable and in-place or not:

Stability:

insertion sort is stable

Suppose the array is:5 2 3 5 1
Let’s distinguish the two 5’s as 5(a) and 5(b) .
So our array is:
5(a)  2 3  5(b)  1

pass 1: 2 5(a) 3 5(b) 1

pass 2: 2 3 5(a) 5(b) 1

pass 3: 2 3 5(a) 5(b) 1

pass 4: 1 2 3 5(a) 5(b)
as you can see in the above example our array is in sorted order and we clearly see that 5(a) comes before 5(b) in initial array and in the sorted array also. So we can clearly see that insertion sort is stable.

In place:

An in-place algorithm is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is usually overwritten by the output as the algorithm executes

Insertion sort is in place, it only requires a constant amount O(1) of additional memory space.