Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
- Simple implementation
- Efficient for (quite) small data sets
- Adaptive (i.e., efficient) for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
- More efficient in practice than most other simple quadratic (i.e., O(n2)) algorithms such as selection sort or bubble sort; the best case (nearly sorted input) is O(n)
- Stable; i.e., does not change the relative order of elements with equal keys
- In-place; i.e., only requires a constant amount O(1) of additional memory space
- Online; i.e., can sort a list as it receives it
ALGORITHM:
insertionSort(array A)
{ This procedure sorts in ascending order. }
begin
for i := 1 to length(A)-1 do
begin
value := A[i];
j := i - 1;
done := false;
repeat
{ To sort in descending order simply reverse
the operator i.e. A[j] < value }
if A[j] > value then
begin
A[j + 1] := A[j];
j := j - 1;
if j < 0 then
done := true;
end
else
done := true;
until done;
A[j + 1] := value;
end;
end;
ANIMATION:
CODE:
/* WWW.CODE-AHOLIC.BLOGSPOT.IN- INSERTIO SORT */
#include<stdio.h>
#include<conio.h>
void main()
{
int i,j,s,temp,a[20];
printf("Enter total elements: ");
scanf("%d",&s);
printf("Enter %d elements: ",s);
for(i=0;i<s;i++)
scanf("%d",&a[i]);
for(i=1;i<s;i++)
{
temp=a[i];
j=i-1;
while((temp<a[j])&&(j>=0))
{
a[j+1]=a[j];
j=j-1;
}
a[j+1]=temp;
}
printf("After sorting: ");
for(i=0;i<s;i++)
printf(" %d",a[i]);
getch();
}