Insertion Sort in c

Insertion sort is a simple sorting algorithm: a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quick sort, heap sort, or merge sort. However, insertion sort provides several advantages:

• simple implementation
• efficient on small data sets
• uses a fixed amount of memory when running

Insertion sort requires the use of two arrays, one ordered, and one unordered. Each repetition of the algorithm moves an item from the unordered list, into a sorted position in the ordered list, until there are no elements left in the unordered list.

Sorting is typically done in-place without needing extra memory. The resulting array after k iterations has the property where the first k + 1 entries are sorted. In each iteration the first remaining entry of the input is removed, inserted into the result at the correct position, thus extending the result:

becomes

with each element greater than x copied to the right as it is compared against x.

Ex :

The following table shows the steps for sorting the sequence {5, 7, 0, 3, 4, 2, 6, 1}. For each iteration, the number of positions the inserted element has moved is shown in parentheses. Altogether this amounts to 17 steps.

5 7 0 3 4 2 6 1 (0)

5 7 0 3 4 2 6 1 (0)

0 5 7 3 4 2 6 1 (2)

0 3 5 7 4 2 6 1 (2)

0 3 4 5 7 2 6 1 (2)

0 2 3 4 5 7 6 1 (4)

0 2 3 4 5 6 7 1 (1)

0 1 2 3 4 5 6 7 (6)

Output :

Code :

#include <stdio.h>

int main()
{
  int n, c, d, t;

  printf("Enter number of elements\n");
  scanf("%d", &n);
  int array[n];
  printf("Enter %d integers\n", n);

  for (c = 0; c < n; c++)
  {
    scanf("%d", &array[c]);
  }

  for (c = 1 ; c <= n - 1; c++)
  {
    d = c;
    while ( d > 0 && array[d] < array[d-1])
    {
      t          = array[d];
      array[d]   = array[d-1];
      array[d-1] = t;

      d--;
    }
  }

  printf("Sorted list in ascending order:\n");

  for (c = 0; c <= n - 1; c++)
    printf("%d\t", array[c]);
  return 0;
}