#include "main.h"
#include "insertion.h"

/*
 * dit algoritme heeft een for-lus in een for-lus, waarbij het aantal iteraties
 * van beide for-lussen recht evenredig is met de grootte van de invoer-array.
 * het aantal iteraties van de binneste lus is afhankelijk van de grootte van
 * de 'sub'-array, die met 1 groeit per iteratie van de buitenste for-lus.
 * hierdoor zou een 'exactere' manier om het aantal stappen te beschrijven
 * O(0.5 * n^2) zijn, maar omdat constante factoren geen invloed hebben over de
 * big-O notatie wordt dit vereenvoudigd tot O(n^2).
 */

void insertion_sort(int* arr, unsigned size) {
	int tail, inner, temp;
	for (tail = size - 2; tail >= 0; tail--) {
		temp = arr[tail];
		for (inner = tail + 1; inner < size; inner++) {
			if (arr[inner] > temp) break;
			arr[inner - 1] = arr[inner];
		}
		arr[inner - 1] = temp;

		printf("outer: ");
		print_arr(arr, size);
	}
}