🎯 Worum geht's? Klasse 11 · 1 Unterrichtsstunde

Nach dieser Seite kannst du …

  • erklären, wie ein Vergleicher zwei Zahlen ordnet
  • Zahlen durch ein Sortiernetzwerk laufen lassen und prüfen, ob es richtig sortiert
  • begründen, warum Sortiernetzwerke parallel arbeiten können

Vorwissen: Sortieren, Vergleiche

⚡ Sortiernetzwerke als Graph

Graphendarstellung optimaler Sortiernetzwerke (Knoten und gerichtete Kanten)

45
Startknoten
Innerer Knoten
Endknoten
Leitung
Komparator-Datenfluss

📖 Graphen-Darstellung der Sortiernetzwerke

Hier wird das Sortiernetzwerk als gerichteter azyklischer Graph (DAG) dargestellt.

  • Knoten (Kreise): Repräsentieren den Zustand eines Wertes zu einem bestimmten Zeitpunkt (Stufe).
  • Startknoten (Cyan): Die unsortierten Eingabewerte, markiert durch einen Startpfeil.
  • Endknoten (Gelb): Die fertig sortierten Ausgabewerte am Ende des Graphen.
  • Kanten (Pfeile): Zeigen den Datenfluss.
  • Grüne gekreuzte Kanten: Stellen einen Komparator dar. Zwei Knoten werden verglichen: Das Minimum wandert auf dem Pfeil nach oben (kleinerer Index), das Maximum nach unten (größerer Index).