Insertion sort is a simple algorithm that sorts an array
one item at a time. When people manually sort something (for example, a deck of
playing cards), most use a method that is similar to insertion sort. The algorithm
is efficient for small data sets. How insertion sort works:
The second element of an array is compared with the
elements that appear before it (only first element in this case). If the second
element is smaller than first element, second element is inserted in the
position of first element. After first step, first two elements of an array are
sorted.
The third element of an array is compared with the
elements that appears before it (first and second element). If third element is
smaller than first element, it is inserted in the position of first element. If
third element is larger than first element but, smaller than second element, it
is inserted in the position of second element. If third element is larger than
both the elements, it is kept in the position as it is. After second step,
first three elements of an array are sorted.
Similarly, the fourth element of an array is
compared with the elements that appear before it (first, second and third
element). After third step, first four elements of an array are sorted. The
same procedure is applied and that element is inserted in the proper position.
If there are n elements to be sorted, then this
procedure is repeated n-1 times to get sorted list of array. Graphical representation of insertion sort:
#include<stdio.h>
int main() {
int i,j,n,temp,a[200];
printf("Enter How Many Data You Want To Sort:
");
scanf("%d",&n);
if(n<=0) printf("\n\tWrong Input?\n");
else {
printf("\n\nEnter %d elements: ",n);
for(i=0;i<n;i++)
scanf(" %d",&a[i]);
for(i=1;i<n;i++) {
temp=a[i];
j=i-1;
while((temp<a[j])&&(j>=0)) /* To sort in descending order, change temp<a[j] to temp>a[j] only. */
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=temp;
}
printf("\n\nAfter Sorting In Ascending Order:
");
for(i=0;i<n;i++)
printf(" %d",a[i]);
printf("\n\n");
return 0;
}}
Method
2:
#include<stdio.h>
#include<stdlib.h>
int insertionsort(int*,int);
int main() {
int *arr,i,n;
printf("Enter How Many Data You Want To Sort: ");
scanf("%d",&n);
if(n<=0) printf("\n\tWrong Input?\n");
else {
arr=(int*)malloc(n*sizeof(int));
printf("\n\nEnter %d Numbers: ", n);
for(i=0;i<n;i++)
scanf(" %d",(arr+i));
insertionsort(arr,n);
printf("\n\nAfter Sorting In Ascending Order:
");
for(i=0;i<n;i++)
printf(" %d",*(arr+i));
printf("\n\n");
return 0;
}}
int insertionsort(int *arr,int n) {
int i,j,temp;
for(i=1;i<n;i++) {
temp=*(arr+i);
j=i-1;
while(temp<*(arr+j)&&j>=0) /* To sort in descending order, change
temp<*(arr+j) to temp>*(arr+j) only. */
{
*(arr+(j+1))=*(arr+j);
j--;
}
*(arr+(j+1))=temp;
}
return 0;
}