summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--algo1w2/bubble.c28
-rw-r--r--algo1w2/bubble.h3
-rw-r--r--algo1w2/insertion.c28
-rw-r--r--algo1w2/insertion.h3
-rw-r--r--algo1w2/main.c77
-rw-r--r--algo1w2/main.h13
-rw-r--r--algo1w2/selection.c20
-rw-r--r--algo1w2/selection.h3
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);