Insertion Sort - C/C++

Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item 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 ofinversions
  • 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

below is the implementation of Insertion Sort in C


#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
 
int N;
void INSERT(int*);
 
void main()
{
 int *A, i;
 clrscr();
 printf("\n\n ENTER NO OF ELEMENTS : ");
 scanf("%d", &N);
 
 A = (int*)malloc((N + 1)*sizeof(int));
 
 printf("\n ENTER ELEMENTS : \n");
 
 A[0] = -100;
 
 for (i = 1; i <= N; i++)
 {
  printf(" A[%02d] : ", i);
  scanf("%d", &A[i]);
 }
 
 INSERT(A);
 printf("\n SORTED ARRAY :\n");
 
 for (i = 1; i <= N; i++)
 {
  printf("\n A[%02d] : %d", i, A[i]);
 }
 
 getch();
}
 
void INSERT(int *A)
{
 int i, t, j;
 for (i = 2; i <= N; i++)
 {
  t = A[i];
  j = i - 1;
  while (t < A[j])
  {
   A[j + 1] = A[j];
   j--;
  }
  A[j + 1] = t;
 }
}


Check out other methods of sorting in Data Structure :
1. Implementation of Insertion Sort in C
2. Implementation of Selection Sort in C
3. Implementation of Quick Sort in C
4. Implementation of Bubble Sort in C
5. Implementation of Heap sort in C
6. Implementation of Merge Sort in C
7. Implementation of Radix Sort in C

Post a Comment