Merge-Sort in C: Praktische Übung mit Projektorwinkel-Berechnung (COP 3502C)

Merge-Sort in C: So meisterst du die Projektor-Aufgabe (COP 3502C Assignment 4)

Sortieren ist eine der grundlegendsten Fähigkeiten in der C-Programmierung. In diesem Tutorial zeigen wir dir, wie du Merge-Sort einsetzt, um ein realitätsnahes Problem zu lösen: die Berechnung des maximalen Projektorwinkels, bei dem keine Personengruppe im Lichtkegel steht. Die Aufgabe stammt aus dem COP 3502C Assignment 4 und trainiert den Umgang mit struct, atan2, dynamischer Speicherverwaltung und der compareTo-Strategie.

Warum Merge-Sort? Ein Beispiel aus der Gaming-Welt

Stell dir vor, du entwickelst ein Spiel wie Among Us und musst die Spieler nach ihrem Winkel zur Kamera sortieren, um Sichtbarkeit zu berechnen. Oder du arbeitest an einer KI-gesteuerten Drohne, die Personen in einem kreisförmigen Bereich erfasst. Genau solche Szenarien erfordern stabile Sortieralgorithmen wie Merge-Sort. Mit Merge-Sort in C lernst du nicht nur Sortieren, sondern auch, wie du Objekte nach benutzerdefinierten Kriterien ordnest.

Das Problem verstehen: Projektorwinkel und Personengruppen

Gegeben sind N Gruppen mit Koordinaten (x, y) und Personenzahl s. Der Projektor steht im Ursprung (0,0) und strahlt einen Sektor mit Winkelbreite A ab. Ziel ist es, den maximalen Winkel zu finden, bei dem keine Gruppe im Lichtkegel liegt. Zusätzlich müssen alle Paare von Gruppen ausgegeben werden, die diesem maximalen Winkel am nächsten kommen.

Schritt 1: Datenstrukturen definieren

Laut Aufgabenstellung benötigst du zwei struct-Typen. Ein Group-Struct speichert die Gruppennummer, den Winkel (im Bogenmaß) und die Personenzahl. Ein Result-Struct speichert ein Paar von Gruppennummern und den zugehörigen Winkel. Verwende dynamische Speicherverwaltung mit malloc, da die Anzahl der Gruppen erst zur Laufzeit bekannt ist.

typedef struct {
    int groupNumber;
    double angle;   // in radian
    int size;
} Group;

typedef struct {
    int firstGroup;
    int secondGroup;
    double angle;   // in degrees
} Result;

Schritt 2: Winkelberechnung mit atan2

Die Funktion atan2(y, x) aus math.h liefert den Winkel im Bogenmaß zwischen der positiven x-Achse und dem Punkt (x,y). Da Gruppen nie auf derselben Geraden durch den Ursprung liegen, sind alle Winkel eindeutig. Achte darauf, negative Winkel in den Bereich [0, 2π) zu konvertieren.

#include <math.h>
double angle = atan2(y, x);
if (angle < 0) angle += 2 * M_PI;

Schritt 3: Sortieren der Gruppen mit Merge-Sort

Merge-Sort ist ein stabiler, effizienter Sortieralgorithmus mit O(n log n). Du implementierst ihn rekursiv: Teile das Array in zwei Hälften, sortiere diese und merge sie. Die compareTo-Funktion vergleicht zwei Gruppen anhand ihres Winkels. So stellst du sicher, dass die Gruppen nach aufsteigendem Winkel sortiert werden.

int compareTo(Group a, Group b) {
    if (a.angle < b.angle) return -1;
    if (a.angle > b.angle) return 1;
    return 0;
}

Schritt 4: Maximalen Winkel und Paare finden

Nach dem Sortieren iterierst du durch das Array und berechnest die Differenz zwischen aufeinanderfolgenden Winkeln. Die größte Lücke (unter Berücksichtigung des Kreisabschlusses) ist der gesuchte maximale Winkel. Alle Paare, die diese Lücke begrenzen, werden in einem dynamischen Array gespeichert. Zum Schluss sortierst du die Paare nach den Gruppennummern (zuerst nach erster, dann nach zweiter Gruppe).

Schritt 5: Floating-Point-Vergleich und Ausgabe

Runde den maximalen Winkel auf vier Dezimalstellen. Verwende für den Vergleich von Gleitkommazahlen eine kleine Toleranz (z.B. 1e-9), um Rundungsfehler zu vermeiden. Die Ausgabe erfolgt zeilenweise: zuerst den Winkel, dann jedes Paar in aufsteigender Reihenfolge.

Trend-Beispiel: Schulnoten-Sortierung mit Merge-Sort

Stell dir vor, du hast eine Liste von Schülern mit ihren Namen und Noten. Du möchtest sie nach Note sortieren, aber bei gleicher Note alphabetisch. Merge-Sort eignet sich hervorragend, weil er stabil ist – die Reihenfolge gleicher Elemente bleibt erhalten. Genau wie bei der Projektor-Aufgabe definierst du eine compareTo-Funktion, die zuerst die Note und dann den Namen vergleicht.

Häufige Fehler und Tipps

• Vergiss nicht, den Kreisabschluss zu berücksichtigen: Der Winkel zwischen der letzten und ersten Gruppe plus 2π.
• Dynamische Arrays: Alloziere genug Speicher für maximal N Paare, verwende einen Zähler.
• Sortierung der Paare: Verwende einen einfachen Bubble-Sort oder qsort mit eigener compare-Funktion.
• atan2 vs. atan: Immer atan2(y, x) verwenden, da es den Quadranten korrekt berücksichtigt.

Fazit

Mit diesem Tutorial hast du gelernt, wie du Merge-Sort in C für eine praxisnahe Aufgabe einsetzt. Die Projektor-Winkel-Berechnung kombiniert wichtige Konzepte: dynamische Speicherverwaltung, Vergleichsfunktionen und Sortierung. Diese Fähigkeiten sind auch in der Spieleentwicklung, bei KI-Anwendungen oder in der Finanzanalyse gefragt. Probiere es selbst aus und optimiere deinen Code!