# Insertion Sort in C

Insertion Sort in C

0
0

## Insertion sort in C

Consider first element of the array as sorted then loop through remaining elements and perform insertion like inserting an element is done in a sorted array.

### Important points

• Assume first element to be sorted. Then take each of remaining element and insert in that sorted array.
• Time complexity is of O(n^2).
• Insertion sort is more beneficial in linked lists as there is no need of swapping.
• Stable

### Program for Insertion Sort in C language

``````#include<stdio.h>
#include<stdlib.h>

void InsertionSort(int A[],int n)
{
int i,j,x;
for (i=1;i<n;i++)
{
j=i-1;
x = A[i];
while(j>-1 && A[j]>x)
{
A[j+1] = A[j];
j--;
}
A[j+1] = x;
}
}

int main()
{
int A = {1,5,2,1,6,3,6,2,5,10};
int i;
InsertionSort(A,10);
for(i=0;i<10;i++)
{
printf("%d ",A[i]);
}
return 0;
}``````

## Other sorting algorithms

Count sort in C/C++

Merge sort in C/C++

Quick Sort in C/C++

Selection sort in C/C++

Insertion Sort in C/C++

Bubble Sort in C/C++

Criteria for sorting analysis