You are here

Insertion sort in C

Insertion sort in C: C program for insertion sort to sort numbers. This code implements insertion sort algorithm to arrange numbers of an array in ascending order. With a little modification, it will arrange numbers in descending order. Best case complexity of insertion sort is O(n), average and the worst case complexity is O(n2).

Insertion sort algorithm implementation in C

  1. /* Insertion sort ascending order */
  2.  
  3. #include <stdio.h>
  4.  
  5. int main()
  6. {
  7.   int n, array[1000], c, d, t;
  8.  
  9.   printf("Enter number of elements\n");
  10.   scanf("%d", &n);
  11.  
  12.   printf("Enter %d integers\n", n);
  13.  
  14.   for (c = 0; c < n; c++)
  15.     scanf("%d", &array[c]);
  16.  
  17.   for (c = 1 ; c <= n - 1; c++) {
  18.     d = c;
  19.  
  20.     while ( d > 0 && array[d-1] > array[d]) {
  21.       t          = array[d];
  22.       array[d]   = array[d-1];
  23.       array[d-1] = t;
  24.  
  25.       d--;
  26.     }
  27.   }
  28.  
  29.   printf("Sorted list in ascending order:\n");
  30.  
  31.   for (c = 0; c <= n - 1; c++) {
  32.     printf("%d\n", array[c]);
  33.   }
  34.  
  35.   return 0;
  36. }

Output of program:
Insertion sort C program output

Download Insertion sort program.

Best case complexity of insertion sort is O(n), average and the worst case complexity is O(n2).