Insertion Sort Algorithm

Insertion Sort

A simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quick sort, heap sort or merge sort algorithms. However, insertion sort algorithm provides several advantages:

• Simple Implementation
• Efficient for smaller data sets.
• Efficient for data sets that are already substantially sorted: the time complexity is O(n+d), where d is the number of inversions.
• More efficient in practice than most other simple quadratic algorithms such as selection sort and bubble sort algorithms.
• Stable – doesn’t change the relative order of elements with equal keys

Input

A sequence of n numbers ( a1, a2, a3, ………, a)

Output

A sorted array of elements ( a1′, a2′, a3′, ……., an’ ) of the input sequence such that a1′ <= a2′ <= a3′ <= ………. <= an’

Algorithm

Algorithm for Insertion sort (n elements) is given below:

for j ← 2 to length[A]
do key ← A[j]
Insert A[j] into the sorted sequence A[1 - (j - 1)]
i ← j - 1
while i > 0 and A[i] > key
do A[i+1] ← A[i]
i ← i – 1
A[i + 1] ← key

Explanation

Let us take the example of a list of numbers { 5, 2, 4, 6, 1, 3 }. Now if we take a look at the above algorithm, the index j indicates the current card  being inserted into the array. At the beginning of each iteration of the ” outer for loop ” which is indexed by j, the sub-array consisting of the elements A[1 ….. (j -1)] constitute the currently sorted hand, and elements A[j+1 …. n] correspond to the pile of cards still on the table. In fact, elements A[1 …. (j – 1)] are the elements originally in the positions 1 ( indexed 0 ) through (j – 1), but now in sorted order.

Analysis of Insertion Sort

 Insertion Sort Algorithm Cost Time for j ← 2 to length[A] c1 n do key ← A[j] c2 n-1 Insert A[j] into the sorted sequence A[ 1…. (j – 1) ] – n-1 i ← i – 1 c4 n-1 while i > 0 and A[i] > key c5 Σ Σj to n = pow(2, tj) do A[i+1] ← A[i] c6 Σ Σj to n = pow(2, tj-1) i ← i – 1 c7 Σ Σj to n = pow(2, tj-1) A[i + 1] ← key c8 n-1

We start by presenting the Insertion Sort procedure with the time cost of each statement and the whole number of times each statement is executed. For each j = 2, 3, 4, 5, ………, n, where n is length[A] i.e. length of the array. We let “tj” be the number of times the while loop test in line 5 is executed for that value of “j”. When for or while loop exists in the usual way the test is executed one time more than the loop body. We assume that comments are not executable statements and so they take no time. The running time of the algorithm is the sum of running times for each statement executed; a statement that takes “ci” to the total running time. To compute T(n) , the running time of Insertion sort , we sum the products of the cost and times columns, obtaining:

T(n) = c1(n) + c2(n-1) + c4(n-1) + c5(n-1) + c8(n-1)

T(n) = (c1 + c2 + c4 + c5 + c8) n – (c2 + c4 + c5 + c8)

This running time can be expressed as an+b for constants a and b that depend on the statement costs ci , it is thus linear function of n. If the array is in reverse sorted order that is decreasing order the worst case results. We must compare each element A[j] with each element in the entire sorted sub-array A[1 …. (j-1)] and so tj = j for j = 2, 3, ……, n.

Σ(j=2 to n) j = [n(n+1) / 2 ] -1

Σ(j=2 to n) (j-1) = [n(n-1)/2]

We find that in the worst case , the running time of insertion sort:

T(n) = c1 n + c2(n-1) +c4( n-1) +c5 ( (n(n+1)/2)-1) + c6 ( n(n-1) / 2) + c7 (n(n-1)/2) +c8 (n-1)

T(n) = ([c5 /2] + [c6 /2] + [c7 /2]) n x n + (c1 +c2 +c4 +[c5/2]-[c6/2]-[c7/2]+c8) – (c2 + c4 + c5 +c8)

The worst case running time can be expressed as an2 + bn + c for constants a , b and c that again depend on the statement costs ci; it is thus a quadratic function of n.

Complexity of Insertion Sort

The complexity of any algorithm can be expressed in three ways:

• Best case complexity
• Average case complexity
• Worst case complexity
Best case Complexity

The best case complexity can be calculated where the array is already sorted or the required element is in the first position. Calculating the best case complexity gives us the lower bound of the time. In this case, the insertion sort algorithm has a linear running time (i.e., O(n)). 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.

Best case complexity = O(n)

Worst case Complexity

The worst case complexity can be calculated by assuming that the element is in the last position or the element is not even present in the array. In this cases every iteration of the inner loop will scan and shift the entire sorted sub-section of the array before inserting the next element. This gives insertion sort a quadratic running time (i.e., O(n2))

Worst case Complexity = O(n²)

Average case Complexity

The average case complexity can be calculated by taking the average of the best case and the worst case complexities of any algorithm.