Insertion Sort | Sorting Techniques in Data Structure

2. Insertion Sort

-> Insertion sort is a simple sorting algorithm.
-> This sorting method sorts the array by shifting elements one by one.
-> It builds the final sorted array one item at a time.


-> Insertion sort has one of the simplest implementation.
-> This sort is efficient for smaller data sets but it is insufficient for larger lists.
-> It has less space complexity like bubble sort.
-> It requires single additional memory space.
-> Insertion sort does not change the relative order of elements with equal keys because it is stable.

// C program to implement Insertion sort.


#include<stdio.h>
int main()
{
int a[100],n,i,j,temp;
printf("Enter array  size:");
scanf("%d",&n);
printf("Enter %d numbers:",n);
for(i=0; i<n; i++)
scanf("%d",&a[i]);
for(i=0; i<n; i++)
{
temp=a[i];
for(j=i; j>0 && a[j-1]>temp; j--)
{
a[j]=a[j-1];
}
a[j]=temp;
}
printf("Elements after sorting:\n");
for(i=0; i<n; i++)
printf("%d  ",a[i]);
return 0;
}

OUTPUT:

Enter array  size:6
Enter 6 numbers:40 10 9 20 30 50
Elements after sorting:
9  10  20  30  40  50