2.2 Insertion Sort

/*
The idea is to start iterating from the second element of array
till last element and for every element insert at its correct
position in the subarray before it.(like we do when we play cards)
(Time Complexity:  O(N^2))
*/
#include <stdio.h>

void InsertionSort(int arr[],int n){
    for(int i=1 ; i<n ; i++){
        int current = arr[i];
        int j=i-1;
        while(arr[j]>current && j>=0){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = current;
    }
}
int main()
{
    int n;
    scanf("%d", &n);
    int arr[n];
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

    InsertionSort(arr,n);

    for(int i=0 ; i<n ; i++) printf("%d ",arr[i]);

    return 0;
}