Insertion Sort Algorithm

#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, t_j = 1 for j = 2, 3, ..., n and the best-case running time can be computed using equation (1) as follows:

T(n) = c₁n + c₂ (n − 1) + c₄ (n − 1) + c₅ ∑_{2 ≤ j ≤ n} (1) + c₆ ∑_{2 ≤ j ≤ n} (1 − 1) + c₇ ∑_{2 ≤ j ≤ n} (1 − 1) + c₈ (n − 1)

T(n) = c₁n + c₂ (n − 1) + c₄ (n − 1) + c₅ (n − 1) + c₈ (n − 1)

T(n) = (c₁ + c₂ + c₄  + c₅  + c₈ ) n + (c₂  + c₄  + c₅  + c₈)

This running time can be expressed as an + b for constants a and b that depend on the statement costs c_i. 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 t_j = 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, t_j = j for j = 2, 3, ..., n and the worst-case running time can be computed using equation (1) as follows:

T(n) = c₁n + c₂ (n − 1) + c₄  (n − 1) + c₅ ∑_{2 ≤ j ≤ n} ( j ) + c₆ ∑_{2 ≤ j ≤ n}(j − 1) + c₇ ∑_{2 ≤ j ≤ n}(j − 1) + c₈ (n − 1)

And using the summations in CLRS on page 27, we have

T(n) = c₁n + c₂ (n − 1) + c₄  (n − 1) + c₅ ∑_{2 ≤ j ≤ n} [n(n +1)/2 + 1] + c₆ ∑_{2 ≤ j ≤ n} [n(n − 1)/2] + c₇ ∑_{2 ≤ j ≤ n} [n(n − 1)/2] + c₈ (n − 1)

T(n) = (c₅/2 + c₆/2 + c₇/2) n² + (c₁ + c₂ + c₄ + c₅/2 − c₆/2 − c₇/2 + c₈) n − (c₂ + c₄ + c₅ + c₈)

This running time can be expressed as (an² + bn + c) for constants a, b, and c that again depend on the statement costs c_i. 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) = an² + bn + c = O(n²)

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 t_j  = 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.