Insertion Sort

 3) Insertion Sort

Aim

To arrange elements in ascending order using Insertion Sort (without functions).

Objective

• To learn insertion-based sorting.

• To understand shifting of elements.

Algorithm

1. Input number of elements and array.

2. For i = 1 to n-1

• key = arr[i], j = i-1

• While j >= 0 and arr[j] > key

• arr[j+1] = arr[j]

• j--

• Place key at arr[j+1].

3. Print sorted array.

Flowchart 

Insertion Sort Using C

The below is the implementation of insertion sort using C program:

#include <stdio.h>

int main()

{

    int a[6];

    int key;

    int i, j;

    int temp;

    printf("Enter any six elements to be sorted using insertion sort\n");

    for (i = 0; i < 6; i++) {

        scanf("%d", &a[i]);

    }

    for (j = 1; j < 6; j++) {

        key = a[j];

        i = j - 1;

        while ((i >= 0) && (a[i] >= key)) {

            temp = a[i + 1];

            a[i + 1] = a[i];

            a[i] = temp;

            i = i - 1;

        }

        a[i + 1] = key;

    }

    printf("elements after sorting using insertion sort are \n");

    for (i = 0; i < 6; i++) {

        printf("%d  \n", a[i]);

    }

    return 0;

}