Worst Case,Best Case and Average Case Efficiency using Insertion Sort.

Insertion Sort is based on inserting a single element in the right for a given iteration.

#include<stdio.h>
void sortArray(int arr[],int n)
{
int i,temp,j;
for(i=0;i<n;i++)
{
temp=arr[i];
j=i-1;

while(j>=0 && arr[j]>temp)
{
arr[j+1]=arr[j];
j--;

}
arr[j+1]=temp;

}
}
void printArray(int arr[], int n)
{
   int i;
   for (i=0; i < n; i++)
       printf("%d ", arr[i]);
   printf("\n");
}

int main()
{
int i;
int arr[]={12, 11, 13, 5, 6};

int n=sizeof(arr);
printf("Given Array is:");
for(i=0;i<n;i++)
{
printf("%d\n",arr[i]);
}
sortArray(arr,n);
printArray(arr,n);
}

Explanation:

Best Case:If an input array is already Sorted. The time complexity will be O(n).
Worst Case:If the array is sorted in reverse order.In this case Time Complexity will be O(n2).
Average Case:If the input array consist of random numbers.The Time Complexity is O(n2).