#include<stdio.h>
#include<conio.h>
void insertion(int a[],int n)
{
int i,j,x,k;
for(i=1;i<=n-1;i++)
{
j=i;
x=a[i];
while(a[j-1]>x &&
j>0)
{
a[j]=a[j-1];
j=j-1;
}
a[j]=x;
}
}
void main()
{
int a[100],n,i;
clrscr();
printf("\n\nEnter an integer value for total no.s of elements to be
sorted: ");
scanf("%d",&n);
for(i=0;i<=n-1;i++)
{
printf("\n\nEnter an integer
value for element no.%d: ",i+1);
scanf("%d",&a[i]);
}
insertion(a,n);
printf("\n\n\nFinally sorted array
is : ");
for(i=0;i<=n-1;i++)
{
printf("%4d",a[i]);
}
}
Best-Case
The best case occurs if
the array is already sorted. For each j = 2, 3, ..., n, we find
that A[i] less than or equal to the key when i has its
initial value of (j − 1). In other words, when i = j −1,
always find the key A[i] upon the first time the WHILE loop is
run.
Therefore, tj
= 1 for j = 2, 3, ..., n and the best-case running time can be
computed using equation (1) as follows:
T(n) = c1n
+ c2 (n − 1) + c4 (n − 1) + c5 ∑2
≤ j ≤ n (1) + c6 ∑2 ≤ j ≤
n (1 − 1) + c7 ∑2 ≤ j ≤ n (1
− 1) + c8 (n − 1)
T(n) = c1n
+ 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. Therefore, T(n) it
is a linear function of n.
The punch line here is
that the while-loop in line 5 executed only once for each j. This
happens if given array A is already sorted.
T(n)
= an + b = O(n)
It is a linear function
of n.
Worst-Case
The worst-case occurs if
the array is sorted in reverse order i.e., in decreasing order. In the reverse
order, we always find that A[i] is greater than the key in the
while-loop test. So, we must compare each element A[j] with each
element in the entire sorted subarray A[1 .. j − 1] and so tj
= j for j = 2, 3, ..., n. Equivalently, we can say that
since the while-loop exits because i reaches to 0, there is one
additional test after (j − 1) tests. Therefore, tj = j
for j = 2, 3, ..., n and the worst-case running time can be
computed using equation (1) as follows:
T(n) = c1n
+ c2 (n − 1) + c4 (n −
1) + c5 ∑2 ≤ j ≤ n ( j )
+ c6 ∑2 ≤ j ≤ n(j − 1) + c7
∑2 ≤ j ≤ n(j − 1) + c8 (n
− 1)
And using the summations
in CLRS on page 27, we have
T(n) = c1n
+ c2 (n − 1) + c4 (n −
1) + c5 ∑2 ≤ j ≤ n [n(n
+1)/2 + 1] + c6 ∑2 ≤ j ≤ n [n(n
− 1)/2] + c7 ∑2 ≤ j ≤ n [n(n
− 1)/2] + c8 (n − 1)
T(n) = (c5/2
+ c6/2 + c7/2) n2 + (c1
+ c2 + c4 + c5/2 − c6/2
− c7/2 + c8) n − (c2
+ c4 + c5 + c8)
This running time can be
expressed as (an2 + bn + c) for constants a,
b, and c that again depend on the statement costs ci.
Therefore, T(n) is a quadratic function of n.
Here the punch line is
that the worst-case occurs, when line 5 executed j times for each j.
This can happens if array A starts out in reverse order
T(n)
= an2 + bn + c = O(n2)
Average Case
On average, the key in A[j]
is less than half the elements in A[1 .. j − 1] and it is greater than the other half. It implies
that on average, the while loop has to look halfway through the sorted subarray
A[1 .. j − 1] to decide where to drop key.
This means that tj = j/2.
Although the average-case running time is
approximately half of the worst-case running time, it is still a quadratic
function of n.
