Klausurersatzleistung

Allgemeine Informationen zur Klausurersatzleistung

In der Klausurersatzleistung wird das Thema Sortieralgorithmen behandelt.

Die Note setzt sich aus zwei Teilen zusammen:

Implementierung des Sortieralgorithmus in Processing mit Visualisierung ($\frac{1}{3}$ der Punkte)
Schriftliche Ausarbeitung zum Sortieralgorithmus ($\frac{2}{3}$ der Punkte)

Alle nötigen Informationen zu den Sortieralgorithmen könnt ihr euch im Leitprogramm Sortierverfahren (PDF) erarbeiten. Weitere Informationen findet ihr auf inf-schule.de. Eventuell sind an manchen Stellen zusätzliche Quellen nötig, diese müsst ihr einerseits selbst recherchieren und andererseits auch entsprechend zitieren / angeben.

Implementierung

Die Visualisierung der einzelnen Schritte ist nicht ganz trivial. Hierfür werden Threads benötigt, die im Grundkurs nicht thematisiert werden. In der Hilfe-Box unten (aufklappen!) findet ihr zwei Java-Dateien, die ihr als Grundlage verwenden sollt. Erstellt in Processing einen neuen Sketch und kopiert die Sketch-Datei da hinein. Erstellt dann einen neuen Tab und kopiert die SortingAlgorithm-Datei dort hinein. Diese beiden Dateien müsst ihr weder verstehen noch verändern.

Eure eigene Implementation eines Sortier-Algorithmus erstellt ihr in einem eigenen Tab mit der folgenden Vorlage:

class SortingAlgorithmImplementation extends SortingAlgorithm {
  public void sort() { 
    // Hier kommt eure Implementierung hin
  }
}

Ihr habt zwei Hilfs-Methoden zur Verfügung, die ihr für das korrekte Funktionieren der Visualisierung auch verwenden müsst:

Die Methode int compare(int idxA, int idxB) vergleicht die Array-Einträge an den Stellen idxA und idxB und liefert folgende Rückgabewerte:
- Rückgabewert > 0, wenn array[idxA] > array[idxB]
- Rückgabewert < 0, wenn array[idxA] < array[idxB]
- Rückgabewert 0, wenn array[idxA] = array[idxB]
Die Methode void swap(int idxA, int idxB) vertauscht die beiden Array-Einträge an den Stellen idxA und idxB.

Zusätzlich könnt ihr euch noch Marker definieren, die z.B. den bereits sortierten Bereich kennzeichnen. Hierzu könnt ihr die folgenden Methoden verwenden:

Die Methode void marker(String name, color col) erstellt einen neuen Marker mit dem angegebenen Namen und Farbe
Die Methode void mark(String name, int idx) platziert den Marker mit dem angegebenen Namen am angegebenen Index
Die Methode void unmark(String name) löscht den Marker mit dem angegebenen Namen

Im Interface habt ihr die folgenden Tastenkürzel zur Verfügung:

0 - 4 stellen die Geschwindigkeit ein, mit dem der Sortieralgorithmus abläuft (0 = am schnellsten, 4 = am langsamsten)
r erstellt einen neuen Zufalls-Array, wenn die Simulation nicht gerade läuft.
Leertaste startet die Simulation.

Eine (offensichtlich falsche) Beispielimplementierung für euren Sortier-Algorithmus könnte z.B. so aussehen wie unten. Beachtet im Video die Marker am unteren Bildschirmrand:

Rote Punkte markieren immer, welche beiden Elemente gerade mit swap getauscht werden.
Grüne Punkte markieren immer, welche beiden Elemente gerade mit compare verglichen werden.
Die anderen Punkte sind eure eigenen Marker.

class SortingAlgorithmImplementation extends SortingAlgorithm {
  public void sort() {
    marker("Mitte", #FFFF00);
 
    mark("Mitte", data.length / 2);
 
    if (compare(0, 1) > 0) {
      swap(0, 1);
    }
 
    unmark("Mitte");
 
    // jetzt ist fertig sortiert, oder?! 
  }
}

Interface-Dateien

Sketch

import java.util.concurrent.ConcurrentHashMap;
 
final int LEN = 100;
final int MIN = 1;
final int MAX = 100;
final int OFFSET = 10;
int swapCompareCost = 0;
 
int[] data = null;
SortingAlgorithm sorter;
ConcurrentHashMap<String, Integer> markerColors = new ConcurrentHashMap<>();
ConcurrentHashMap<String, Integer> markerIndices = new ConcurrentHashMap<>();
int compareIdxA = -1;
int compareIdxB = -1;
boolean compareOrSwap = false;
 
void setup() {
  size(640, 480);
  frameRate(120);
  colorMode(HSB, 360, 100, 100);
  ellipseMode(CENTER);
 
  data = newRandomArray();
}
 
void draw() {
  background(0);
 
  if (sorter != null) {
    sorter.step();
  }
 
  float barWidth = (width - 2.0 * OFFSET) / data.length;
  float barHeight = height - 2.0 * OFFSET - barWidth;
  float colorFactor = 360 / MAX;
  float xPos = OFFSET;
 
  for (int i = 0; i < data.length; i++) {
    fill(color(colorFactor * data[i], 100, 100));
    rect(xPos, height - OFFSET - barWidth, barWidth, -(barHeight / MAX) * data[i]);
 
    xPos += barWidth;
  }
 
  float radius = Math.max(5, barWidth / 2);
 
  for (java.util.Map.Entry<String, Integer> entry : markerIndices.entrySet()) {
    String markerName = entry.getKey();
    int markerIdx = entry.getValue();
 
    if (!markerColors.containsKey(markerName)) continue;
 
    color markerColor = markerColors.get(markerName);
 
    fill(markerColor);
    ellipse(OFFSET + barWidth * markerIdx + radius, height - OFFSET - radius, radius, radius);
  }
 
  if (compareIdxA < 0 || compareIdxB < 0) return;
 
  if (compareOrSwap) {
    fill(color(#FF0000));
 
    ellipse(OFFSET + barWidth * compareIdxA + radius, height - OFFSET, radius, radius);
    ellipse(OFFSET + barWidth * compareIdxB + radius, height - OFFSET, radius, radius);
  } else {
    fill(color(#00FF00));
 
    ellipse(OFFSET + barWidth * compareIdxA + radius, height - OFFSET, radius, radius);
    ellipse(OFFSET + barWidth * compareIdxB + radius, height - OFFSET, radius, radius);
  }
}
 
void clearMarkers() {
  compareIdxA = -1;
  compareIdxB = -1;
  markerColors.clear();
  markerIndices.clear();
}
 
void keyPressed() {
  switch (key) {
    case '0':
      swapCompareCost = 0;
      break;
    case '1':
      swapCompareCost = 100;
      break;
    case '2':
      swapCompareCost = 250;
      break;      
    case '3':
      swapCompareCost = 500;
      break;      
    case '4':
      swapCompareCost = 1000;
      break;      
    case 'r':
      if (sorter == null || sorter.isFinished()) {
        data = newRandomArray();
      }
      break;
    case ' ':
      if (sorter == null || sorter.isFinished()) {
        sorter = new SortingAlgorithmImplementation();    
        sorter.setData(data);
        sorter.start();
      }
      break;
  }
}
 
int[] newRandomArray() {
  int[] a = new int[LEN];
 
  for (int i = 0; i < a.length; i++) {
    a[i] = (int)Math.floor(Math.random() * (MAX - MIN) + MIN); 
  }
 
  return a;
}

SortingAlgorithm

abstract class SortingAlgorithm extends Thread {
  public int[] data;
  private boolean finished = true;
  private volatile boolean threadShouldWait = true;
 
  public void setData(int[] data) {
    this.data = data;
  }
 
  public abstract void sort();
 
  public void run() {
    clearMarkers();
    finished = false;
    this.sort();    
    finished = true;
    clearMarkers();
  }
 
  public boolean isFinished() {
    return finished;
  }
 
  public void step() {
    this.threadShouldWait = false;
  }
 
  private void sleepFor(int milliSeconds) {
    try {
      Thread.sleep(milliSeconds);
    } catch (InterruptedException e) {
    }
  }
 
  private void waitForNextStep() {
    while(this.threadShouldWait == true) {
      sleepFor(1);
    }
 
    this.threadShouldWait = true;
  }
 
  public void marker(String name, color col) {
    markerColors.put(name, col);
  }
 
  public void mark(String name, int idx) {
    waitForNextStep();
 
    markerIndices.put(name, idx);
  }
 
  public void unmark(String name) {
    waitForNextStep();
 
    markerIndices.remove(name);
  }
 
  public int compare(int idxA, int idxB) {
    if (idxA == idxB) return 0;
 
    waitForNextStep();
 
    compareIdxA = idxA;
    compareIdxB = idxB;
    compareOrSwap = false;
 
    sleepFor(swapCompareCost);
 
    return this.data[idxA] - this.data[idxB];
  }
 
  public void swap(int idxA, int idxB) {
    if (idxA == idxB) return;
 
    waitForNextStep();
 
    compareIdxA = idxA;
    compareIdxB = idxB;
    compareOrSwap = true;
 
    sleepFor(swapCompareCost);
 
    int tmp = this.data[idxA];
    this.data[idxA] = this.data[idxB];
    this.data[idxB] = tmp;
  }
}

Ausarbeitung

Zusätzlich zur Implementierung muss eine schriftliche Ausarbeitung angefertigt werden. Der Aufbau der Ausarbeitung besteht aus folgenden Punkten:

Deckblatt
Funktionsweise des Sortieralgorithmus
Analyse des Algorithmus bezüglich best- und worst-case (Leitprogramm ab S. 56)
Quellenangabe

Der Umfang der Ausarbeitung beträgt mindestens 2 bis maximal 3 Seiten.

Die Form der Ausarbeitung orientiert sich an denen einer wissenschaftlichen Hausarbeit. Näheres dazu findet ihr hier (PDF).

Bewertungskriterien Implementierung

Gesamt	9
ausführliche Kommentare	3
korrekte Funktion	3
korrekte Visualisierung	3

Bewertungskriterien Ausarbeitung

Gesamteindruck und formales Äußeres
Werden die gültigen Vorgaben zur Gestaltung einer wissenschaftlichen Arbeit eingehalten? (Deckblatt, Inhaltsverzeichnis/ Gliederung, Literaturliste)	1
Sind die Zitate exakt wiedergegeben, mit genauer Quellenangabe?	1
Zeigt die Arbeit insgesamt ein einheitliches Layout?	1
Beschreibung des Algorithmus
Wird der Algorithmus in der Ausarbeitung korrekt beschrieben	8
Werden Randfälle (z.B. vorsortierte Liste) beachtet?	2
Analyse des Algorithmus
Laufzeitanalyse	5
Gesamt	18