Insertion Sort Using C programming.

 Insertion sort is a simple sorting algorithm that works similar to the way you sort playing cards in your hands. The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.

Insertion Sort Algorithm

To sort an array of size N in ascending order iterate over the array and compare the current element (key) to its predecessor, if the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Source Code:-

#include<stdio.h>

void InsertionSort(int a[], int n){

    int i, j, temp;

    for (int i=1; i<n; i++){

        temp = a[i];

        j=i-1;

        while(j>=0 && a[j]>temp){

            a[j+1] = a[j];

            j--;

        }

        a[j+1] = temp;

    }

}

int main() {

    int n;

    printf("Enter the length of the array : ");

    scanf("%d", &n);

    int arr[n];

    printf("Enter the elements : ");

    for (int i=0; i<n; i++){

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

    }

    InsertionSort(arr, n);

    printf("The sorted array is :\n");

    for (int i=0; i<n; i++){

        printf("%d ", arr[i]);

    }

    return 0;

}

Output :-

Enter the length of the array : 5 Enter the elements : 4 7 3 1 9 The sorted array is : 1 3 4 7 9