Sortieren von 2D-Punkten: Median-Koordinaten mit Selection, Insertion, Merge und Quick Sort (Java)

Einführung: Sortieren von 2D-Punkten und Medianbestimmung

In der Informatik ist das Sortieren von Daten eine grundlegende Operation. In diesem Tutorial lernst du, wie du einen Satz von 2D-Punkten mit ganzzahligen Koordinaten sortierst, um den Median-Koordinatenpunkt (MCP) zu finden. Der MCP ist der Punkt, dessen x-Koordinate der Median aller x-Koordinaten und dessen y-Koordinate der Median aller y-Koordinaten ist. Dieses Problem stammt aus einer typischen Hausaufgabe (Coms228 homework 2) und wird hier Schritt für Schritt erklärt, ohne die gesamte Lösung vorzugeben.

Stell dir vor, du entwickelst eine KI für ein Echtzeit-Strategiespiel, das die Positionen von Einheiten auf einer Karte analysiert. Der Median-Koordinatenpunkt könnte den zentralen Punkt einer Truppenformation angeben – nützlich für KI-Entscheidungen. Oder in einer Finanz-App, die Aktienkurse als Punkte in einem 2D-Raum darstellt: Der Medianpunkt repräsentiert die durchschnittliche Kursbewegung.

Projektübersicht und Annahmen

Das Ziel ist es, einen Satz von 2D-Punkten mit ganzzahligen Koordinaten im Bereich -50 bis 50 zu verarbeiten. Die Punkte werden entweder zufällig generiert oder aus einer Datei eingelesen. Du musst vier Sortieralgorithmen implementieren: Selection Sort, Insertion Sort, Merge Sort und Quick Sort. Jeder Algorithmus wird zweimal angewendet: einmal zum Sortieren nach x-Koordinate und einmal nach y-Koordinate. Die medianen Koordinaten werden dann aus den sortierten Arrays extrahiert.

Wichtige Annahmen: Alle Punkte haben ganzzahlige Koordinaten zwischen -50 und 50. Die Eingabe kann doppelte Punkte enthalten. Der Medianindex ist bei n Punkten floor(n/2) (0-basierter Index).

Die Point-Klasse und Vergleichsmethoden

Die Point-Klasse implementiert das Comparable-Interface. Die compareTo()-Methode vergleicht zwei Punkte zuerst nach x, bei Gleichheit nach y. Dies ist entscheidend für die Sortierung. Du musst auch einen Comparator bereitstellen, der nach x oder y allein vergleicht, da die Sortierung nach einer Koordinate erfolgen soll.

public class Point implements Comparable<Point> {
    private int x, y;
    public Point(int x, int y) { this.x = x; this.y = y; }
    public int getX() { return x; }
    public int getY() { return y; }
    @Override
    public int compareTo(Point other) {
        if (this.x != other.x) return Integer.compare(this.x, other.x);
        return Integer.compare(this.y, other.y);
    }
}

Abstrakte Sorter-Klasse und Unterklassen

Die abstrakte Klasse AbstractSorter enthält ein Array points[], eine Variable algorithm und einen Comparator. Der Konstruktor kopiert das übergebene Array und wirft eine IllegalArgumentException, wenn das Array null oder leer ist. Die Methode setComparator() setzt den Comparator (nach x oder y). Die Methode sort() wird in den Unterklassen implementiert. Nach dem Sortieren gibt getMedian() das Element am Medianindex zurück.

protected AbstractSorter(Point[] pts) throws IllegalArgumentException {
    if (pts == null || pts.length == 0) throw new IllegalArgumentException();
    points = new Point[pts.length];
    for (int i = 0; i < pts.length; i++) points[i] = pts[i];
}

Die vier Unterklassen (SelectionSorter, InsertionSorter, MergeSorter, QuickSorter) erben von AbstractSorter und implementieren sort() mit dem jeweiligen Algorithmus. Jeder Konstruktor ruft super(pts) auf und setzt algorithm.

Die PointScanner-Klasse und der Scan-Vorgang

Die Klasse PointScanner führt die beiden Sortierdurchläufe durch. Sie hat zwei Konstruktoren: einen, der ein Point-Array akzeptiert, und einen, der eine Datei einliest. Die Datei enthält abwechselnd x- und y-Koordinaten. Bei einer ungeraden Anzahl von Ganzzahlen wird eine InputMismatchException geworfen. Nach dem Einlesen werden die Punkte in einem Array gespeichert.

Die Methode scan() führt die beiden Sortierungen durch: zuerst nach x, dann nach y. Dabei wird die Zeit mit System.nanoTime() gemessen. Nach jeder Sortierung wird der Medianpunkt über getMedian() ermittelt. Der endgültige Median-Koordinatenpunkt wird aus den beiden Medianen gebildet.

Beispiel aus der Praxis

Angenommen, du hast 17 Punkte aus einer Datei eingelesen (wie im Assignment). Die x-Koordinaten sind: 0, -3, 0, 8, 3, -6, -2, 10, -7, 5, 7, 10, -7, 0, -1, -10, 5. Nach dem Sortieren ergibt sich der Median x = 0 (Index 8). Die y-Koordinaten: 0, -9, -10, 4, 3, 3, 1, 5, -10, -2, 3, 5, -10, 8, -6, 0, 5 → Median y = 1. Der MCP ist (0,1).

Vergleich der Sortieralgorithmen

Die Klasse CompareSorters führt mehrere Durchläufe durch, bei denen die vier Algorithmen auf dieselben Daten angewendet werden. Die Laufzeiten werden verglichen. Dies ist typisch für Algorithmenanalyse in der Informatik. Du kannst beobachten, dass Merge Sort und Quick Sort bei großen Datenmengen schneller sind als Selection und Insertion Sort. Aber bei kleinen Arrays (wie hier mit maximal 10.201 Punkten) sind die Unterschiede gering.

Ein aktuelles Beispiel: In der Spieleentwicklung (z.B. bei der Kollisionserkennung in einem Battle-Royale-Spiel) müssen tausende Spielerpositionen sortiert werden. Ein effizienter Algorithmus wie Quick Sort spielt eine entscheidende Rolle für die Performance.

Implementierungstipps

• Fehlerbehandlung: Überprüfe, ob die Datei existiert und eine gerade Anzahl von Ganzzahlen enthält.
• Comparator: Verwende Comparator.comparingInt(Point::getX) für x und entsprechend für y.
• Medianindex: Bei n Punkten ist der Medianindex (n-1)/2 (0-basiert, da ganzzahlige Division).
• Zeitmessung: Rufe System.nanoTime() vor und nach jeder Sortierung auf und addiere die Differenzen.

Zusammenfassung

In diesem Tutorial hast du gelernt, wie man 2D-Punkte sortiert und den Median-Koordinatenpunkt mit vier verschiedenen Algorithmen bestimmt. Diese Konzepte sind nicht nur für Hausaufgaben relevant, sondern auch für reale Anwendungen in KI, Gaming und Finanzanalyse. Durch das Verständnis der Sortieralgorithmen und ihrer Effizienz kannst du bessere Software entwickeln.

Als Nächstes könntest du die Algorithmen mit zufälligen Daten testen und die Laufzeiten vergleichen. Viel Erfolg bei deiner Implementierung!