1 files changed, 111 insertions, 0 deletions
diff --git a/algo1w3/IntLinkedList.cpp b/algo1w3/IntLinkedList.cpp
new file mode 100644
index 0000000..ce63a6d
--- /dev/null
+++ b/algo1w3/IntLinkedList.cpp
@@ -0,0 +1,111 @@
+#include <iostream>
+
+#include "IntLinkedList.h"
+#include "IntLink.h"
+
+IntLinkedList::IntLinkedList() { }
+
+IntLinkedList::~IntLinkedList() {
+	IntLink* node = this->next;
+	while (node != nullptr) {
+		IntLink* next = node->next;
+		delete node;
+		node = next;
+	}
+}
+
+IntLink* IntLinkedList::getAt(int index) const {
+	if (this->size == 0) return nullptr;
+	IntLink* out = this->next;
+	for (size_t i = 0; i < this->size; i++) {
+		if (out == nullptr) return nullptr;
+		if (i > 0) out = out->next;
+		if (i == index) return out;
+	}
+	return nullptr;
+}
+
+bool IntLinkedList::setAt(int index, int value) {
+	IntLink* node = getAt(index);
+	if (node == nullptr) return false;
+	node->value = value;
+	return true;
+}
+
+int IntLinkedList::length1() const {
+	size_t accu = 0;
+	IntLink* node = this->next;
+	while (node != nullptr) {
+		accu++;
+		node = node->next;
+	}
+	return accu;
+}
+
+int IntLinkedList::length2() const {
+	return this->size;
+}
+
+void IntLinkedList::bubbleSort() {
+	int outer, inner;
+	bool sorted;
+	for (outer = 0; outer < this->size - 2; outer++) {
+		sorted = true; // check if array was modified during inner loop
+		for (inner = this->size - 2; inner >= outer; inner--) {
+			IntLink* inner_node = getAt(inner);
+			if (inner_node->value >= inner_node->next->value) {
+				std::swap(inner_node->value, inner_node->next->value);
+				sorted = false;
+			}
+		}
+		printf("outer %d:  ", outer);
+		showAll();
+		if (sorted) break; // break if nothing changed (already sorted)
+	}
+}
+
+/*
+ * geschatte snelheid van dit algoritme: O(n^3)
+ *
+ * onderbouwing:
+ *
+ * bubble sort is O(n^2), de getAt functie is O(n). getAt wordt afhankelijk van
+ * de grootte van de array een aantal keer uitgevoerd, n^2 * n == n^3 -> O(n^3)
+ */
+
+ /*
+ * metingen van de duur van het sorteren...
+ *
+ * aantal waarden: duur in us:
+ * 1000   114410
+ * 2000   275901
+ * 5000   1443233
+ * 10000  5585394
+ * ...
+ */ 
+
+/*
+ * gemeten snelheid van dit algoritme: O(n^3)
+ * onderbouwing:
+ *
+ * ik heb google spreadsheets gebruikt om de metingen om te zetten naar een
+ * grafiek, en vervolgens een automatische trendlijn te laten maken. bij een
+ * exponentiele lijn is er nog wat afwijking van de metingen, terwijl er bij de
+ * kwadratische lijn geen afwijking is.
+ */
+
+void IntLinkedList::addToStart(int value) {
+	this->next = new IntLink(value, this->next);
+	this->size++;
+}
+
+void IntLinkedList::showAll() const {
+	std::cout << "[";
+	IntLink* node = this->next;
+	while (node != nullptr) {
+		std::cout << node->value;
+		node = node->next;
+		if (node != nullptr) std::cout << ", ";
+	}
+	std::cout << "]" << std::endl;
+}