From d50c5a1af8be6ae51fec28e8b24dfea5ca591906 Mon Sep 17 00:00:00 2001 From: lonkaars Date: Fri, 10 Feb 2023 11:52:16 +0100 Subject: week 2 deel 2 klaar --- algo1w2/bubble.c | 28 +++++++++++++++++++ algo1w2/bubble.h | 3 +++ algo1w2/insertion.c | 28 +++++++++++++++++++ algo1w2/insertion.h | 3 +++ algo1w2/main.c | 77 +++++++++++++++++------------------------------------ algo1w2/main.h | 13 +++++++++ algo1w2/selection.c | 20 ++++++++++++++ algo1w2/selection.h | 3 +++ 8 files changed, 123 insertions(+), 52 deletions(-) create mode 100644 algo1w2/bubble.c create mode 100644 algo1w2/bubble.h create mode 100644 algo1w2/insertion.c create mode 100644 algo1w2/insertion.h create mode 100644 algo1w2/main.h create mode 100644 algo1w2/selection.c create mode 100644 algo1w2/selection.h (limited to 'algo1w2') 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 -#include -#include +#include +#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 +#include +#include + +#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); -- cgit v1.2.3