Normalerweise unterrichte ich in der Jahrgangsstufe 12 nur die Grundkurse. Im Schuljahr 2018/19 musste ich auch den Leistungskurs unterrichten. Hier geht es im Wesentlichen um die Modellierung mit UML und die Implementation, bei uns in C#.
Wichtige Themen sind hierbei der Begriff „Objekt“ und „Klasse“. Darauf aufbauend geht es um die Beziehungen zwischen Klassen wie Vererbung, Assoziation, Aggregation und Komposition und deren Implementation in C#.
Zur Realisierung von 1-zu-N-Beziehungen sind außer den Arrays aich generische Container-Klassen ein Thema. Wie solch ein „Abstrakter Datentyp“ (ADT) List, Stack oder Queue arbeitet, demonstriere ich mit der Projektmappe Generics. Hierin sind drei eigene Implementationen dieser Container in Form einer Template-Klasse implementiert.
Wer sich das mal ansehen will, findet nachfolgend die Visual-Studio-Projektmappe.
Im Hinblick auf das Suchen und Sortieren wird auch das Thema „Komplexität von Algorithmen“ angesprochen.
Für das Thema „Suchen“ (lineares und binäres Suche) sowie für das Sortieren habe ich Klassen entworfen und Testprogramme geschrieben.
Sowohl die Klassen als auch die Projektmappen stehen hinter den PDFs zum Download bereit.
Zur Demonstration der Sortierverfahren habe ich ein GUI-Programm geschrieben, welche die Algorithmen animiert darstellt. Hier ein Screenshot dazu:
Nachfolgend mein Unterrichtsskript:
using System;
namespace Lineare_Suche
{
// Der Datentyp T muss das das Interface
// IComparable implementieren
public static class LinearSeek<T> where T:IComparable
{
public static int FoundIndex { get; private set; }
public static bool IsFound { get; private set; }
public static bool Seek(T[] array, T seekelement)
{
// Guard Clauses
if (array == null) throw new ArgumentNullException("array");
if (seekelement == null) throw new ArgumentNullException("seekelement");
FoundIndex = 0;
IsFound = false;
foreach (T item in array)
{
if (item.CompareTo(seekelement) == 0)
{
IsFound = true;
break;
}
FoundIndex++;
}
return IsFound;
}
}
}using System;
namespace Binäre_Suche
{
public static class BinarySeek<T> where T : IComparable
{
public static int FoundIndex { get; private set; }
public static bool IsFound { get; private set; }
public static int SeekSteps { get; private set; }
private static int mitte;
public static bool SeekIterative(T[] array, T seekelement)
{
// Guard Clauses
if (array == null) throw new ArgumentNullException("array");
if (seekelement == null) throw new ArgumentNullException("seekelement");
FoundIndex = 0;
IsFound = false;
SeekSteps = 0;
int unteregrenze = 0;
int oberegrenze = array.Length - 1;
while (unteregrenze <= oberegrenze)
{
mitte = unteregrenze + (oberegrenze - unteregrenze) / 2;
// array[mitte] < seekelement --> -1
// array[mitte] > seekelement --> 1
// array[mitte] = seekelement --> 0
int rc = array[mitte].CompareTo(seekelement);
if (rc == 1)
oberegrenze = mitte - 1;
else if (rc == -1)
unteregrenze = mitte + 1;
else
{
FoundIndex = mitte;
IsFound = true;
break;
}
SeekSteps++;
}
return IsFound;
}
public static bool SeekRecursive(T[] array, T seekelement)
{
// Guard Clauses
if (array == null) throw new ArgumentNullException("array");
if (seekelement == null) throw new ArgumentNullException("seekelement");
FoundIndex = 0;
IsFound = false;
return BinarySearch(array, 0, array.Length - 1, seekelement);
}
private static bool BinarySearch(T[] array, int untereGrenze, int obereGrenze, T seekelement)
{
if (untereGrenze > obereGrenze)
return false;
mitte = untereGrenze + (obereGrenze - untereGrenze) / 2;
// array[mitte] < seekelement --> -1
// array[mitte] > seekelement --> 1
// array[mitte] = seekelement --> 0
int rc = array[mitte].CompareTo(seekelement);
if (rc == 1)
{
SeekSteps++;
return BinarySearch(array, untereGrenze, mitte - 1, seekelement);
}
if (rc == -1)
{
SeekSteps++;
return BinarySearch(array, mitte + 1, obereGrenze, seekelement);
}
FoundIndex = mitte;
IsFound = true;
return IsFound;
}
}
}using System;
namespace BubbleSort
{
public enum Direction
{
Ascend, Descend
};
public struct BubblesortStatistics
{
public long Steps;
public long Exchanges;
}
// Der Datentyp T muss das das Interface
// IComparable implementieren
public static class Bubblesort<T> where T : IComparable
{
private static Direction direction;
public static Direction Direction
{
get { return direction; }
set { direction = value; }
}
private static BubblesortStatistics statistics;
static Bubblesort()
{
direction = Direction.Ascend;
}
public static BubblesortStatistics Sort(T[] data, Direction _direction)
{
direction = _direction;
return Sort(data);
}
public static BubblesortStatistics Sort(T[] data)
{
// Guard Clause
if (data == null) throw new ArgumentNullException("data");
foreach (T item in data)
{
if (item == null) throw new NullReferenceException();
}
statistics.Steps = 0;
statistics.Exchanges = 0;
// Temporäres Speicherelement
// für den Tauschvorgang
T tmp;
for (int i = data.Length; i > 1; i--)
{
for (int j = 0; j < i - 1; j++)
{
statistics.Steps++;
if (direction == Direction.Ascend)
{
// Aufsteigend sortieren
if (data[j].CompareTo(data[j + 1]) > 0)
{
statistics.Exchanges++;
// Es muss getauscht werden
tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
}
}
else
{
// Absteigend sortieren
if (data[j].CompareTo(data[j + 1]) < 0)
{
statistics.Exchanges++;
// Es muss getauscht werden
tmp = data[j];
data[j] = data[j + 1];
data[j + 1] = tmp;
}
}
}
}
return statistics;
}
}
}using System;
namespace InsertionSort
{
public enum Direction
{
Ascend, Descend
};
public static class Insertionsort<T> where T : IComparable
{
private static int sizeOfArray;
private static Direction direction;
public static Direction Direction
{
get { return direction; }
set { direction = value; }
}
static Insertionsort()
{
direction = Direction.Ascend;
}
public static void Sort(T[] data, Direction _direction)
{
direction = _direction;
Sort(data);
}
public static void Sort(T[] data)
{
sizeOfArray = data.Length;
T t;
for (int i = 1; i < sizeOfArray; i++)
{
int j = i;
t = data[j];
if (direction == Direction.Ascend)
{
while (j > 0)
{
if (data[j - 1].CompareTo(t) > 0)
{
data[j] = data[j - 1];
j -= 1;
}
else
break;
}
}
else
{
while ((j > 0) && (data[j - 1].CompareTo(t) < 0))
{
data[j] = data[j - 1];
j -= 1;
}
}
data[j] = t;
}
}
}
}using System;
namespace QuickSort
{
public enum Direction
{
Ascend, Descend
};
public enum Pivot
{
First, Middle, Last
};
// basierend auf
// www.iti.fh-flensburg.de/lang/algorithmen/sortieren/quick/quick.htm
public static class Quicksort<T> where T : IComparable
{
private static int sizeOfArray;
private static Direction direction;
public static Direction Direction
{
get { return direction; }
set { direction = value; }
}
private static Pivot pivot;
public static Pivot Pivot
{
get { return pivot; }
set { pivot = value; }
}
private static long RecursionDeepness { get; set; }
static Quicksort()
{
direction = Direction.Ascend;
pivot = Pivot.Middle;
}
public static long Sort(T[] data, Direction _direction)
{
RecursionDeepness = 0;
direction = _direction;
return Sort(data);
}
public static long Sort(T[] data, Direction _direction, Pivot _pivot)
{
RecursionDeepness = 0;
direction = _direction;
pivot = _pivot;
return Sort(data);
}
public static long Sort(T[] data)
{
// Guard clauses
if (data == null) throw new ArgumentNullException("data");
foreach (T item in data)
{
if (item == null) throw new NullReferenceException();
}
sizeOfArray = data.Length;
QuickSort(data, 0, sizeOfArray - 1);
return RecursionDeepness;
}
private static void QuickSort(T[] data, int untereGrenze, int obereGrenze)
{
RecursionDeepness++;
int i = untereGrenze, j = obereGrenze;
T x = default(T);
if (pivot == Pivot.First)
{
// Vergleichselement (Pivot) x ist erstes Element
x = data[untereGrenze];
}
else if (pivot == Pivot.Middle)
{
// Vergleichselement (Pivot) x liegt in der Mitte
x = data[untereGrenze + (obereGrenze - untereGrenze) / 2];
}
else if (pivot == Pivot.Last)
{
// Vergleichselement (Pivot) x ist letztes Element
x = data[obereGrenze];
}
// Aufteilung
while (i <= j)
{
if (direction == Direction.Ascend)
{
while (data[i].CompareTo(x) == -1) i++;
while (data[j].CompareTo(x) == 1) j--;
if (i <= j)
{
Exchange(data, i, j);
i++; j--;
}
}
else
{
while (data[i].CompareTo(x) == 1) i++;
while (data[j].CompareTo(x) == -1) j--;
if (i <= j)
{
Exchange(data, i, j);
i++; j--;
}
}
}
// Rekursion
if (untereGrenze < j) QuickSort(data, untereGrenze, j);
if (i < obereGrenze) QuickSort(data, i, obereGrenze);
}
private static void Exchange(T[] data, int i, int j)
{
T t = data[i];
data[i] = data[j];
data[j] = t;
}
}
}using System;
namespace ShellSort
{
public enum Direction
{
Ascend, Descend
};
// basierend auf
// www.iti.fh-flensburg.de/lang/algorithmen/sortieren/shell/shell.htm
public static class Shellsort<T> where T : IComparable
{
private static int sizeOfArray;
private static Direction direction;
public static Direction Direction
{
get { return direction; }
set { direction = value; }
}
static Shellsort()
{
direction = Direction.Ascend;
}
public static void Sort(T[] data, Direction _direction)
{
direction = _direction;
Sort(data);
}
public static void Sort(T[] data)
{
sizeOfArray = data.Length;
int i, j, columns;
T t;
//Spaltenanzahl
int[] cols = {1391376, 463792, 198768, 86961, 33936,
13776, 4592, 1968, 861, 336, 112, 48,
21, 7, 3, 1};
foreach (int colvalue in cols)
{
columns = colvalue;
for (i = columns; i < sizeOfArray; i++)
{
j = i;
t = data[j];
if( direction==Direction.Ascend)
{
while ((j >= columns) && (data[j - columns].CompareTo(t) > 0))
{
data[j] = data[j - columns];
j = j - columns;
}
}
else
{
while ((j >= columns) && (data[j - columns].CompareTo(t) < 0))
{
data[j] = data[j - columns];
j = j - columns;
}
}
data[j] = t;
}
}
}
}
}