From 1e8670763d8387e6416334f0dbdb909f4b51fb76 Mon Sep 17 00:00:00 2001 From: Loek Le Blansch Date: Sat, 14 Sep 2024 16:23:17 +0200 Subject: add week 2 --- week2/Bubblesort.cs | 19 ++++++++++++++++++ week2/Mergesort.cs | 53 ++++++++++++++++++++++++++++++++++++++++++++++++ week2/Program.cs | 58 +++++++++++++++++++++++++++++++++++++++++++++++++++++ week2/Quicksort.cs | 55 ++++++++++++++++++++++++++++++++++++++++++++++++++ week2/readme.md | 54 +++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 239 insertions(+) create mode 100644 week2/Bubblesort.cs create mode 100644 week2/Mergesort.cs create mode 100644 week2/Program.cs create mode 100644 week2/Quicksort.cs create mode 100644 week2/readme.md (limited to 'week2') 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> picks = new List> { + // new Tuple(leftIndex, list[leftIndex]), + // new Tuple(middle, list[middle]), + // new Tuple(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 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + +
QuicksortQuicksort3MergesortBubblesort
gesorteerdgeshuffledgesorteerdgeshuffledgesorteerdgeshuffledgesorteerdgeshuffled
Aantal vergelijkingen502498201781000916637--499500498870
Aantal swaps50037205003218--499500244380
Uitvoertijd132.5 ms7.330 ms4.360 ms8.580 ms30.91 ms33.52 ms304.5 ms254.1 ms
+ -- cgit v1.2.3