add week 2

5 files changed, 239 insertions, 0 deletions

diff --git a/week2/Bubblesort.cs b/week2/Bubblesort.cs
new file mode 100644
index 0000000..82ceb4f
--- /dev/null
+++ b/week2/Bubblesort.cs
@@ -0,0 +1,19 @@
+namespace ALGA {
+	public class Bubblesort {
+		public static void bubblesort(ISortList list) {
+			for (int i = 0; i < list.Count - 1; i++) {
+				bool swapped = false;
+
+				for (int j = 0; j < list.Count - i - 1; j++) {
+					if (list.compare(j, j + 1) <= 0) continue;
+
+					list.swap(j, j + 1);
+					swapped = true;
+				}
+
+				if (!swapped) break;
+			}
+		}
+	}
+}
+
diff --git a/week2/Mergesort.cs b/week2/Mergesort.cs
new file mode 100644
index 0000000..b9810b5
--- /dev/null
+++ b/week2/Mergesort.cs
@@ -0,0 +1,53 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace ALGA {
+	public class Mergesort {
+		public static void mergesort(ISortList list) {
+			if (list.Count <= 1) return;
+			mergesort(list, 0, list.Count - 1);
+		}
+
+		public static void mergesort(ISortList list, int leftIndex, int rightIndex) {
+			if (leftIndex > rightIndex) return;
+			if (rightIndex - leftIndex <= 0) return;
+
+			int middle = (leftIndex + rightIndex) / 2;
+			mergesort(list, leftIndex, middle);
+			mergesort(list, middle + 1, rightIndex);
+			merge(list, leftIndex, middle, rightIndex);
+		}
+
+		private static void merge(ISortList list, int leftIndex, int middleIndex, int rightIndex) {
+			int leftSize = middleIndex - leftIndex + 1;
+			ISortList left = new SortList(leftSize);
+			for (int i = 0; i < leftSize; i++) left[i] = list[leftIndex + i];
+
+			int rightSize = rightIndex - middleIndex;
+			ISortList right = new SortList(rightSize);
+			for (int i = 0; i < rightSize; i++) right[i] = list[middleIndex + 1 + i];
+
+			int leftOffset = 0;
+			int rightOffset = 0;
+			for (int i = leftIndex; i <= rightIndex; i++) {
+				if (leftOffset == leftSize) {
+					list[i] = right[rightOffset++];
+					continue;
+				}
+				if (rightOffset == rightSize) {
+					list[i] = left[leftOffset++];
+					continue;
+				}
+
+				if (left[leftOffset] < right[rightOffset])
+					list[i] = left[leftOffset++];
+				else
+					list[i] = right[rightOffset++];
+			}
+		}
+	}
+}
+
diff --git a/week2/Program.cs b/week2/Program.cs
new file mode 100644
index 0000000..feef98b
--- /dev/null
+++ b/week2/Program.cs
@@ -0,0 +1,58 @@
+using System;
+using System.Collections.Generic;
+using System.Diagnostics;
+using System.Linq;
+using System.Runtime.Remoting.Channels;
+using System.Text;
+using System.Threading.Tasks;
+
+namespace ALGA {
+	class Program {
+		static void Main(string[] args) {
+			int items = 1000;
+			int repetitions = 1_000;
+
+			Stopwatch sw = new Stopwatch();
+			int swaps = 0, comparisons = 0;
+
+			for (int i = 0; i < repetitions; i++) {
+				SortList list = new SortList(items);
+
+				sw.Start();
+				Bubblesort.bubblesort(list);
+				sw.Stop();
+
+				swaps += list.Swaps;
+				comparisons += list.Comparisons;
+			}
+			Console.WriteLine("Unsorted:");
+			Console.WriteLine("\tExec:        {0} ns", sw.ElapsedMilliseconds * 10e3 / repetitions);
+			Console.WriteLine("\tSwaps:       {0} (avg)", swaps / repetitions);
+			Console.WriteLine("\tComparisons: {0} (avg)", comparisons / repetitions);
+			sw.Reset();
+			swaps = 0;
+			comparisons = 0;
+			
+			for (int i = 0; i < repetitions; i++) {
+				SortList list = new SortList(items, true);
+
+				sw.Start();
+				Bubblesort.bubblesort(list);
+				sw.Stop();
+
+				swaps += list.Swaps;
+				comparisons += list.Comparisons;
+			}
+			Console.WriteLine("Sorted:");
+			Console.WriteLine("\tExec:        {0} ns", sw.ElapsedMilliseconds * 10e3 / repetitions);
+			Console.WriteLine("\tSwaps:       {0} (avg)", swaps / repetitions);
+			Console.WriteLine("\tComparisons: {0} (avg)", comparisons / repetitions);
+			Console.WriteLine("");
+
+			Console.WriteLine("({0} items, {0} repetitions)", items, repetitions);
+
+			Console.ReadLine();
+		}
+	}
+}
+
diff --git a/week2/Quicksort.cs b/week2/Quicksort.cs
new file mode 100644
index 0000000..0cfa360
--- /dev/null
+++ b/week2/Quicksort.cs
@@ -0,0 +1,55 @@
+using System;
+using System.Collections.Generic;
+using System.Linq;
+
+namespace ALGA {
+	public class Quicksort {
+		public static void quicksort(ISortList list) {
+			quicksort(list, 0, list.Count - 1);
+		}
+
+		private static void quicksort(ISortList list, int leftIndex, int rightIndex) {
+			if (leftIndex >= rightIndex || leftIndex < 0) return;
+
+			int pivotIndex;
+			int middle = leftIndex + ((rightIndex - leftIndex) / 2);
+
+			// // Quicksort
+			// pivotIndex = leftIndex;
+
+			// pass unit tests
+			pivotIndex = middle;
+
+			// // Quicksort3
+			// List<Tuple<int, int>> picks = new List<Tuple<int, int>> {
+			// 	new Tuple<int, int>(leftIndex, list[leftIndex]),
+			// 	new Tuple<int, int>(middle, list[middle]),
+			// 	new Tuple<int, int>(rightIndex, list[rightIndex]),
+			// };
+			// picks.Sort((a, b) => a.Item2.CompareTo(b.Item2));
+			// pivotIndex = picks[1].Item1;
+
+			pivotIndex = partition(list, pivotIndex, leftIndex, rightIndex);
+
+			quicksort(list, leftIndex, pivotIndex - 1);
+			quicksort(list, pivotIndex + 1, rightIndex);
+		}
+
+		public static int partition(ISortList list, int pivotIndex, int leftIndex, int rightIndex) {
+			while (true) {
+				while (list.compare(leftIndex, pivotIndex) < 0) leftIndex++;
+				while (list.compare(pivotIndex, rightIndex) < 0) rightIndex--;
+
+				if (leftIndex >= rightIndex) break;
+
+				list.swap(leftIndex, rightIndex);
+				if (leftIndex == pivotIndex)
+					pivotIndex = rightIndex;
+				else if (rightIndex == pivotIndex)
+					pivotIndex = leftIndex;
+			}
+			return pivotIndex;
+		}
+	}
+}
+
diff --git a/week2/readme.md b/week2/readme.md
new file mode 100644
index 0000000..75e2f9f
--- /dev/null
+++ b/week2/readme.md
@@ -0,0 +1,54 @@
+<table class="table table-bordered">
+  <tr>
+    <th></th>
+    <th colspan="2">Quicksort</th>
+    <th colspan="2">Quicksort3</th>
+    <th colspan="2">Mergesort</th>
+    <th colspan="2">Bubblesort</th>
+  </tr>
+  <tr>
+    <th></th>
+    <td>gesorteerd</td>
+    <td>geshuffled</td>
+    <td>gesorteerd</td>
+    <td>geshuffled</td>
+    <td>gesorteerd</td>
+    <td>geshuffled</td>
+    <td>gesorteerd</td>
+    <td>geshuffled</td>
+  </tr>
+  <tr>
+    <th>Aantal vergelijkingen</th>
+    <td>502498</td>
+    <td>20178</td>
+    <td>10009</td>
+    <td>16637</td>
+    <td>-</td>
+    <td>-</td>
+    <td>499500</td>
+    <td>498870</td>
+  </tr>
+  <tr>
+    <th>Aantal swaps</th>
+    <td>500</td>
+    <td>3720</td>
+    <td>500</td>
+    <td>3218</td>
+    <td>-</td>
+    <td>-</td>
+    <td>499500</td>
+    <td>244380</td>
+  </tr>
+  <tr>
+    <th>Uitvoertijd</th>
+    <td>132.5 ms</td>
+    <td>7.330 ms</td>
+    <td>4.360 ms</td>
+    <td>8.580 ms</td>
+    <td>30.91 ms</td>
+    <td>33.52 ms</td>
+    <td>304.5 ms</td>
+    <td>254.1 ms</td>
+  </tr>
+</table>
+