Insertion Sort Algorithm (DSA) C lang.🌟🌟👍⌚

 By: Himanshu Tiwari

Insertion sort is a simple sorting algorithm that works by iteratively inserting each element of an unsorted list into its correct position in a sorted portion of the list. It is a stable sorting algorithm, meaning that elements with equal values maintain their relative order in the sorted output.

ALGORITHM : 

• We have to start with second element of the array as first element in the array is assumed to be sorted.
• Compare second element with the first element and check if the second element is smaller then swap them.
• Move to the third element and compare it with the second element, then the first element and swap as necessary to put it in the correct position among the first three elements.
• Continue this process, comparing each element with the ones before it and swapping as needed to place it in the correct position among the sorted elements.
• Repeat until the entire array is sorted.

#include<stdio.h>

void printarr(int arr[], int n){

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

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

    }

    printf("\n");

}

void insertionsort(int arr[],int n){

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

        int key=arr[i];

        int j=i-1;

        while (j>=0 && arr[j]>key){

            arr[j+1]=arr[j];

            j--;

        }

        arr[j+1]=key;

       

       

    }

}

int main(){

    int arr[]={54,25,86,94,3,4};

    int n=6;

    printarr(arr,n);

    insertionsort(arr,n);

    printarr(arr,n);

    return 0;

}