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

int N;
void INSERT(int*);
void main()
 int *A, i;
 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]);
 printf("\n SORTED ARRAY :\n");
 for (i = 1; i <= N; i++)
  printf("\n A[%02d] : %d", i, A[i]);
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];
  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