1 files changed, 28 insertions, 0 deletions
diff --git a/algo1w2/insertion.c b/algo1w2/insertion.c
new file mode 100644
index 0000000..d484f11
--- /dev/null
+++ b/algo1w2/insertion.c
@@ -0,0 +1,28 @@
+#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);
+	}
+}
+