week 2 deel 2 klaar

8 files changed, 123 insertions, 52 deletions

diff --git a/algo1w2/bubble.c b/algo1w2/bubble.c
new file mode 100644
index 0000000..43890fd
--- /dev/null
+++ b/algo1w2/bubble.c
@@ -0,0 +1,28 @@
+#include "main.h"
+#include "bubble.h"
+
+void bubble_sort(int* arr, unsigned size) {
+	// index array (stabiliteit)
+	// int* indices = malloc(size * sizeof(int));
+	// for (unsigned i = 0; i < size; i++) indices[i] = i;
+
+	int outer, inner;
+	bool sorted;
+	for (outer = 0; outer < size - 2; outer++) {
+		sorted = true; // check if array was modified during inner loop
+		for (inner = size - 2; inner >= outer; inner--) {
+			if (arr[inner] >= arr[inner+1]) {
+				swap(arr[inner], arr[inner+1]);
+				// swap(indices[inner], indices[inner+1]); // swap indices array (stabiliteit)
+				sorted = false;
+			}
+		}
+		printf("outer %d:  ", outer);
+		print_arr(arr, size);
+		// print index array (stabiliteit)
+		// printf("index %d:  ", outer);
+		// print_arr(indices, size);
+		if (sorted) break; // break if nothing changed (already sorted)
+	}
+}
+
diff --git a/algo1w2/bubble.h b/algo1w2/bubble.h
new file mode 100644
index 0000000..6c3838f
--- /dev/null
+++ b/algo1w2/bubble.h
@@ -0,0 +1,3 @@
+#pragma once
+
+void bubble_sort(int*, unsigned);
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);
+	}
+}
+
diff --git a/algo1w2/insertion.h b/algo1w2/insertion.h
new file mode 100644
index 0000000..6771d82
--- /dev/null
+++ b/algo1w2/insertion.h
@@ -0,0 +1,3 @@
+#pragma once
+
+void insertion_sort(int*, unsigned);
diff --git a/algo1w2/main.c b/algo1w2/main.c
index 19d2138..84eb41f 100644
--- a/algo1w2/main.c
+++ b/algo1w2/main.c
@@ -1,67 +1,40 @@
-#include <stdio.h>
-#include <stdbool.h>
-#include <stdlib.h>
+#include <memory.h>
+#include "main.h"
 
-// https://stackoverflow.com/questions/8862136/is-there-a-built-in-swap-function-in-c
-#define swap(a, b) { (a) = (a) ^ (b); (b) = (a) ^ (b); (a) = (b) ^ (a); }
-
-void print_arr(int* arr, unsigned size);
-
-void bubble_sort(int* arr, unsigned size) {
-	// index array (stabiliteit)
-	// int* indices = malloc(size * sizeof(int));
-	// for (unsigned i = 0; i < size; i++) indices[i] = i;
-
-	int outer, inner;
-	bool sorted;
-	for (outer = 0; outer < size - 2; outer++) {
-		sorted = true; // check if array was modified during inner loop
-		for (inner = size - 2; inner >= outer; inner--) {
-			if (arr[inner] >= arr[inner+1]) {
-				swap(arr[inner], arr[inner+1]);
-				// swap(indices[inner], indices[inner+1]); // swap indices array (stabiliteit)
-				sorted = false;
-			}
-		}
-		printf("outer %d:  ", outer);
-		print_arr(arr, size);
-		// print index array (stabiliteit)
-		// printf("index %d:  ", outer);
-		// print_arr(indices, size);
-		if (sorted) break; // break if nothing changed (already sorted)
-	}
-}
-
-/*
- * ik heb een tweede array aangemaakt met allen indexgetallen, en elke keer als
- * er ge`swap`t wordt swap ik ook de array met indices. hierdoor heb ik na het
- * uitvoeren van het algoritme een array waarin elke waarde de oorspronkelijke
- * index van elke waarde uit de uitvoer-array bevat:
- *
- * unsorted: [7, 3, 8, 3, 3, 5, 4, 6, 3, 0]
- * sorted:   [0, 3, 3, 3, 3, 4, 5, 6, 7, 8]
- * indexes:  [9, 8, 4, 3, 1, 6, 5, 7, 0, 2]
- *               ^  ^  ^  ^  deze zijn op volgorde van groot naar klein
- *
- * na het uitvoeren van "de test", zie ik dat alle '3'-en in de array met
- * indices van groot naar klein gesorteerd zijn, en niet op een willekeurige
- * volgorde. hieruit concludeer ik dat dit sorteeralgoritme stabiel is.
- */
+#include "bubble.h"
+#include "selection.h"
+#include "insertion.h"
 
 int main() {
-	int arr[] = { 7, 3, 8, 1, 2, 5, 4, 6, 9, 0 }; // array van opdracht 1
-	// int arr[] = { 7, 3, 8, 3, 3, 5, 4, 6, 3, 0 }; // array om stabiliteit te testen
-	unsigned size = sizeof(arr) / sizeof(int);
+	const int original[] = { 7, 3, 8, 1, 2, 5, 4, 6, 9, 0 };
+	const unsigned size = sizeof(original) / sizeof(int); // array lengte (niet sizeof)
+	int* arr = malloc(sizeof(original));
+	memcpy(arr, original, sizeof(original));
 
 	printf("unsorted: ");
 	print_arr(arr, size);
 	printf("\n");
 
+	printf("-- bubble sort --\n");
 	bubble_sort(arr, size);
+	printf("sorted:   ");
+	print_arr(arr, size);
 	printf("\n");
 
-	printf("sorted:   ");
+	memcpy(arr, original, sizeof(original)); // reset array
+	printf("-- selection sort --\n");
+	selection_sort(arr, size);
+	printf("sorted: ");
 	print_arr(arr, size);
+	printf("\n");
+
+	memcpy(arr, original, sizeof(original)); // reset array
+	printf("-- insertion sort --\n");
+	insertion_sort(arr, size);
+	printf("sorted:");
+	print_arr(arr, size);
+	printf("\n");
+
 
 	return 0;
 }
diff --git a/algo1w2/main.h b/algo1w2/main.h
new file mode 100644
index 0000000..4bc71fd
--- /dev/null
+++ b/algo1w2/main.h
@@ -0,0 +1,13 @@
+#pragma once
+
+#include <stdio.h>
+#include <stdbool.h>
+#include <stdlib.h>
+
+#define swap(a, b) { int t = (a); (a) = (b); (b) = (t); }
+
+#define min(a, b) (((a) < (b)) ? (a) : (b))
+#define max(a, b) (((a) > (b)) ? (a) : (b))
+
+void print_arr(int*, unsigned);
+
diff --git a/algo1w2/selection.c b/algo1w2/selection.c
new file mode 100644
index 0000000..ba706f0
--- /dev/null
+++ b/algo1w2/selection.c
@@ -0,0 +1,20 @@
+#include "main.h"
+#include "selection.h"
+
+unsigned smallest_index(int* arr, unsigned size) {
+	if (size == 0) return 0;
+	unsigned min_idx = 0;
+	for (unsigned i = 0; i < size; i++)
+		if (arr[i] <= arr[min_idx])
+			min_idx = i;
+	return min_idx;
+}
+
+void selection_sort(int* arr, unsigned size) {
+	for (unsigned tail = 0; tail < size; tail++) {
+		unsigned smallest = tail + smallest_index(&arr[tail], size - tail);
+		swap(arr[tail], arr[smallest]);
+		printf("tail %d: ", tail);
+		print_arr(arr, size);
+	}
+}
diff --git a/algo1w2/selection.h b/algo1w2/selection.h
new file mode 100644
index 0000000..bfba3c7
--- /dev/null
+++ b/algo1w2/selection.h
@@ -0,0 +1,3 @@
+#pragma once
+
+void selection_sort(int*, unsigned);