Insertion Sort Algorithm :
Insertion Sort Algorithm INSERTION-SORT(A)
For j ← 2 to length [A]
key ← A[j]
Put A[j] into the sorted sequence A[1 . . j -1]
i ← j -1
while i > 0 and A[i] > key
A[i+1] ← A[i]
i ← i-1
A[i+1] ← key
Insertion Sort Continue :
Insertion Sort Continue Input Size
More input more time.
Running Time
The number of primitive operations or steps executed during a program execution is the running time of algorithm.
Analysis of Insertion Sort :
Analysis of Insertion Sort INSERTION-SORT(A)
for j ← 2 to n
key ← A[ j ]
Insert A[ j ] into the sorted sequence A[1 . . j -1]
i ← j - 1
while i > 0 and A[i] > key
A[i + 1] ← A[i]
i ← i – 1
A[i + 1] ← key cost times
c1 n
c2 n-1
0 n-1
c4 n-1
c5
c6
c7
c8 n-1 4
Insertion Sort Continue :
Insertion Sort Continue T(n) = c1n + c2(n – 1) + c4(n – 1) + c5 + c6 + c7 + c8(n – 1)
Best Case Analysis
For Best Case tj=1. Putting the value of tj=1 in the above equation we get
T(n) = c1n + c2(n – 1) + c4(n – 1) + c5(n - 1) + c8(n – 1)
= (c1 + c2 + c4 + c5 + c8)n – (c2 + c4 + c5 + c8)
The above best case running time can be expressed as an+b. Thus it is a linear function of n.
T(n) = Θ(n)
Insertion Sort Continue :
Insertion Sort Continue T(n) = c1n + c2(n – 1) + c4(n – 1) + c5 + c6 + c7 + c8(n – 1)
Worst Case Analysis
For worst case tj = j. So
= = and (Mathematical Proof)
= = (Mathematical Proof)
Putting these values in the above equation will give us the following
T(n) = c1n +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)
= (c5/2 + c6/2 + c7/2)n2 + (c1 + c2 + c4 + c5/2 – c6/2 – c7/2 + c8)n - (c2 + c4 + c5 + c8)
The above worse case running time can be expressed as an2 + bn + c. So It is quadratic function of n
T(n) = Θ(n2)
Insertion Sort Continue :
Insertion Sort Continue Order Of Growth Ө
If an algorithm has lower order of growth for its worst case analysis, then that algorithm is more efficient than another.
The worst case running time for insertion sort is
an2 + bn + c
= an2 ( lower-order terms are insignificant for larger no. of inputs.)
= Ө (n2)
Insertion sort will run more quickly in the worst case than a Ө( n3) algorithm.