#include <stdio.h>
	#include <stdlib.h>

	// Function Prototypes
	void insertionSort(int *arr, int len);

	void insertionSort(int *arr, int len) {
		int i, j, hand;
		for (i = 1; i < len; i++) {
			hand = arr[i];
			j = i - 1;

			while (j >= 0 && arr[j] > hand) {
				arr[j + 1] = arr[j];
				j--;
			}

			arr[j + 1] = hand;
		}
	}

	void printArr(int *arr, int len) {
		for (int i = 0; i < len; i++)
			printf("%d ", arr[i]);
		printf("\n\n");
	}

	int main(void) {
		int len = 20;
		int *arr = malloc(len * sizeof(int));
		for (int i = 0; i < len; i++) {
			arr[i] = rand() % 100;
		}
		printf("Printing Array...\n\n");
		printArr(arr, len);
		printf("Applying Insertion Sort...\n\n");
		insertionSort(arr, len);
		printf("Printing Sorted Array...\n\n");
		printArr(arr, len);
		free(arr);
		return 0;
	}