In insertion sorting technique, the elements are scanned from left to right and insert each element in its proper location in the previously sorted list. So in an array Arr of n number of elements Arr[1] is assumed to be sorted. Then in the second iteration Arr[2] is inserted either before Arr[1] or after Arr[1] so that Arr[1] and Arr[2] are sorted. Similarly Arr[3] will be inserted either before Arr[1] , after Arr[3] or between Arr[1] and Arr[2] and so on. Now the problem is , where to insert Arr[x] in an sorted sub-array. This can be achieved by comparing Arr[x] with Arr[x-1] , Arr[x-2],Arr[x-3] and so on until it meets a value that less than or equal to Arr[x].Suppose Arr[j] is such value. Then Arr[x] will be positioned at Arr[j+1] location and all elements with which Arr[x] was compared will move forward by one location. From the above it is clear that there must be always an element Arr[j] such that Arr[j]<=Arr[x].So always put some small number say 0 in Arr[0] so that the above condition will be useful.
C Program on insertion sort
# include < stdio.h>
#define number 10
/* actually 11 values will be inserted in this array, value in the 0 index being a small value (0)*/
void iS(int arr[], int n)
{
int p,temp,i,k,x;
arr[0] = 0;
for(i = 1 ; i <= n; i++)
{
x=0;
p= i -1;
temp = arr[i];
/* In the iteration of the loop 'p' is 0 and 'i' is 1.So 'temp' will be the second element of the array , means the first valid value of the array while 'arr[p]' will be the smallest value (-0).So in the first iteration there will be no interchange of values. */
while(temp < arr[p])
{
arr[p+1] = arr[p];
p --;
x++;
/* In the second iteration,'arr[i]' means the second valid value while 'arr[p]' is the value of the previous location.The loop will continue to search the location for 'temp' if 'temp' is less than its previous value and during this process the greater values will be shifted one location right until the specific value 'temp' becomes equal to or greater than its previous value. At the end set 'temp' in its proper location with the statement 'arr[p+1]=temp' */
}
arr[p+1] = temp;
printf("Step(%d):-", i);
for(k = 1; k <= n; k++)
printf(" %d", arr[k]);
if(x!=0)
printf("-- took %d comparisions to place %d.",x,temp);
else
printf("--No interchange of position for %d.",temp);
printf("\n");
}
}
void display(int arr[], int n)
{
int i;
printf("\n Sorted list is as follows\n");
for(i = 1; i <= n; i++)
printf(" %d", arr[i]);
}
void main()
{
int list[20];
int i;
clrscr();
printf("\n Number of elements in the list: %i", number);
printf("\n Enter ten values:-\n");
for(i = 1; i <= number; i++)
{
scanf("%d",&list[i]);
}
printf("\n Step wise result is as follows \n\n");
iS(list,number);
display(list, number);
getch();
}
Insertion sort program without any extra location
#include < stdio.h>
void ins(int arr[],int n)
{
int i,j,k,t,flag;
for(i=1;i< n;i++)
{
k=0;
flag=0;
while(1)
{
if(i< k)
break;
/* means there is no smaller value at left side of the value positioned at location 'i'*/
if(arr[i]< arr[k])
{
t=arr[k];
arr[k]=arr[i];
/* take the value to be shifted right side in 't' and insert the value of location 'i' at the location 'k' */
flag=1;
}
if(flag==1)
{
for(j=i;j>k+1;j--)
{
arr[j]=arr[j-1];
/* this shifts the values in the right ward direction */
}
arr[j]=t;
/* positioning the value lifted from the left side to just right of it */
}
else
k++;
/* trying with next value */
if(flag==1)
break;
/* in case of shifting, try with another value */
}
}
}
void main()
{
int i,arr[10];
clrscr();
for(i=0;i<10;i++)
{
printf("\nValue=");
scanf("%d",&arr[i]);
}
printf("\nBEFORE SORTING\n");
for(i=0;i<10;i++)
printf("%4d",arr[i]);
ins(arr,10);
printf("\nAFTER SORTING\n");
for(i=0;i<10;i++)
printf("%4d",arr[i]);
getch();
}
Algorithm of Insertion Sort :- ARR is an array which holds N+1 number of values.ARR[0] is made to store a very small value , so actual values stored in the array is N.TEMP is a variable which will help to interchange values while required. I is loop control variable. P is another variable.
Repeat the following steps for I=1,2,3…N
Set TEMP=ARR[I]
Set P=I-1
While TEMP < ARR[P]
Set ARR[P+1]=ARR[P]
Set P=P-1
[End of inner loop]
Set ARR[P]=TEMP
[End of outer loop]
End
Complexity of insertion sort:
In worst case while the list is arranged in reversed order, the inner loop will make k-1 comparisons to set the value of kth position in its actual location. So the time complexity f(x)=1+2+3+….+(n-1)
=n(n-1)/2
=O(n2)
In average case, there will be approximately (k-1)/2 comparisons for each element to set the value in its position. So f(x)=1/2+2/2+3/2+……(n-1)/2
= n(n-1)/4
=O(n2)
No comments:
Post a Comment