diff options
| -rw-r--r-- | week2/Bubblesort.cs | 19 | ||||
| -rw-r--r-- | week2/Mergesort.cs | 53 | ||||
| -rw-r--r-- | week2/Program.cs | 58 | ||||
| -rw-r--r-- | week2/Quicksort.cs | 55 | ||||
| -rw-r--r-- | week2/readme.md | 54 |
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> + |