summaryrefslogtreecommitdiff
path: root/week2
diff options
context:
space:
mode:
Diffstat (limited to 'week2')
-rw-r--r--week2/Bubblesort.cs19
-rw-r--r--week2/Mergesort.cs53
-rw-r--r--week2/Program.cs58
-rw-r--r--week2/Quicksort.cs55
-rw-r--r--week2/readme.md54
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>
+