Sortiernetzwerke

[Mike M. (mikeii)]

Könnte mir mal bitte jemand auf die Sprünge helfen?
Es geht darum, ein Sortiernetzwerk mit 4 Schlüsseln zu finden, welches 
Sortiert.
Hat man das, soll man die Tiefe bestimmen und die Größe.
Man soll nun beweisen, dass diese Werte minimal sind.

Mein Sortiernetzwerk sieht so aus:

--o-----o-------
  |     |
--|--o--o--o----
  |  |     |
--o--|--o--o----
     |  |
-----o--o-------

Als Tiefe habe ich 3, als Größe 5

Warum die Tiefe 3 Minimal ist, habe ich so begründet:
Sämtliche Möglichkeiten für ein Netzwerk der Tiefe 2 sortiert nicht, da 
es in jeder Variante mindestens einen Eingang gibt, der nicht alle 
Ausgänge erreichen könnte.

Das Problem ist jetzt die Größe, warum brauche ich minimal 5 
Vergleichern? Bzw, ist 5 überhaupt maximal, oder gibt es eine 
Möglichkeit mit 4 Vergleichern?

Gruß Mike

[Yalu X. (yalu) (Moderator)]

Wieviele verschiedene Umstellmöglichkeiten braucht man, um n Elemente
aus jeder beliebigen Reihenfolge in eine sortierte Reihenfolge
überzuführen?

Und wieviele verschiedene Umstellmöglichkeiten sind mit k Komparatoren
maximal realisierbar?

Aus den Antworten auf diese Fragen lässt sich eine untere Abschätzung
für k ableiten.

[Mike M. (mikeii)]

>Wieviele verschiedene Umstellmöglichkeiten braucht man, um n Elemente
>aus jeder beliebigen Reihenfolge in eine sortierte Reihenfolge
>überzuführen?

2^n Stück oder hab ich die Frage falsch verstanden?


>Und wieviele verschiedene Umstellmöglichkeiten sind mit k Komparatoren
>maximal realisierbar?

2^k ?

Ich stehe etwas auf dem Schlauch was genau Umstellmöglichkeiten heißt. 
Meinst du damit ein Element auf einen neuen Platz, oder die Tauschung?



Danke für deine Hilfe:)

[Yalu X. (yalu) (Moderator)]

Mir ist vorhin leider kein besserer Begriff als "Umstellmöglichkeiten"
eingefallen. Ich hätte stattdessen "unterscheidbare Fälle" schreiben
sollen. Was ich gemeint habe:

Die 4 Elemente können auf 4!=24 verschiedene Weisen angeordnet sein.
Also muss der Sortierer mindestens 24 Fälle unterscheiden können.

>> Und wieviele verschiedene Umstellmöglichkeiten sind mit k Komparatoren
>> maximal realisierbar?
>
> 2^k ?

Genau. Jeder Komparator kann zwei Fälle unterscheiden: Entweder stehen
die beiden Eingangswerte in der richtigen Reihenfolge oder nicht. 4
Komparatoren können also 2⁴=16 Fälle unterscheiden. Da 16<24 ist, kann
nicht jede Eingangspermutation individuell behandelt werden, so dass ein
Sortierer der Größe 4 nicht erfolgreich sein kann. Folglich braucht man
mindestens 5 Komparatoren. Dass damit das Problem tatsächlich lösbar
ist, hast du ja bereits anhand eines Beispiels gezeigt.

Also ist 5 die minimale Größe des Sortierers.

[Mike M. (mikeii)]

Mensch Danke! Sehr gut erklärt, jetzt sieht das ganze schon viel 
einfacher aus :)

Danke und gute Nacht :)