Correctness and the Loop Invariant : HackerRank Problem Solution

Correctness and the Loop Invariant : HackerRank Problem Solution

C++ Implementation:


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
#include <assert.h>

void insertionSort(int N, int arr[]) {
    int i,j;
    int value;
    for(i=1;i<N;i++)
    {
        value=arr[i];
        j=i;
        while(j>0 && value<arr[j-1])
        {
            arr[j]=arr[j-1];
            j=j-1;
        }
        arr[j]=value;
    }
    for(j=0;j<N;j++)
    {
        printf("%d",arr[j]);
        printf(" ");
    }
}
int main(void) {

    int N;
    scanf("%d", &N);
    int arr[N], i;
    for(i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }

    insertionSort(N, arr);

    return 0;
}