INSERTION SORTING: – An insertion sort is one that sorts a set of records by inserting records into an existing sorted file. If the initial file is sorted only one comparison is made on each pass so that the sort is O (N). If the file is initially sorted in reverse order, the sort is O (N²). The simple insertion sort is still usually better than the bubble sort. The closer the file is to sorted order, the more efficient the simple insertion sort becomes. The average number of comparisons in the simple insertion sort (by considering all possible permutations of the input array) is also O (n²). The space requirements for the sort consist of only one temporary variable.
Both the selection sort and the simple insertion sort are more efficient than the bubble sort Selection sort requires fewer assignments than insertion sort but more companions The insertion sort algorithm is a very slow algorithm when n is very large. Insertion sort is usually used only when n is small. This algorithm is very popular with bridge players when they first sort their cards In this procedure, we pick up a particular value and then insert it at the appropriate place in the sorted sub-list. The worst-case performance occurs when the input array elements are in descending order. The first pass makes 1 comparison, the second pass makes 2 and the last pass makes an N – 1 comparison. So total comparisons are 1.2 * [N – 2) (N – 1) = NIN – 1 / 2 = O (N²).
Algorithm – Insertion sorting in c.
INSERTION_SORT (A, N).
Here A is an array with N elements. This algorithm sorts the array A with N elements in ascending order.
1. Repeat Steps 2 to 5 for I=2 to N
2. Set ITEM: = A [1].
3. Set J: = 1-1.
4. Repeat Steps while J > = 1 AND A [J] > ITEM:
(a) Set A [J + 1] = A [J]. [Moves element forward.]
(b) Set J: = J – 1.
[End of Step 4 loop]
5. Set A [J + 1]: = ITEM. [Inserts element in the proper place.]
[End of Step 1 loop.]
6. Return.
Insertion sorting program in C.
#include<stdio.h>
#include<conio.h>
#define SIZE 10
void insertion_sort(int [],int);
void main()
{
int a[SIZE],i,n;
clrscr();
printf("Enter how many elements");
scanf("%d",&n);
/*Input Array */
for(i=0;i<n;i++)
{
printf("Enter element %d ",i+1);
scanf("%d",&a[i]);
}
insertion_sort(a,n);
/* Output Array */
for(i=0;i<n;i++)
printf("%d",a[i]);
getch();
}
void insertion_sort(int a[], int n)
{
int i,j,item;
for(i=1;i<n;i++)
{
item = a[i];
/*Shifting */
for(j=i-1;j>=0 && a[j] > item; j--)
a[j+1] = a[j];
/* insert */
a[j+1] = item;
}
}Also, Read