[midas]

Hi!

Ich habe diese Aufgabenstellung bekommen und muss die machen, ich bastle daran schon seit Tagen rum, ich hoffe irgendwer kann mir von euch helfen.

Die Zeilen einer 2-dimensionalen Reihung ("Matrix") int[][] a sollen lexikographisch geordnet werden. Beispiel:

vorher: {{8,1,-11,234}, nachher: {{1,20,0,1111},
{1,20,0,1111}, {8,1,-11,234},
{8,1,122,100}} {8,1,122,100}}

Es gibt mehrere algorithmische Möglichkeiten; hier zwei Beispiele, die min-sort benutzen:
a) Ordnen Sie die Zeilen nach der letzten, dann nach der vorletzten usw. Position. Sie können dafür jeweils min-sort verwenden, wenn Sie durch eine kleine Änderung sicherstellen, dass bei der Sortierung nach der k-ten Position Zeilen mit gleichem Wert auf dieser Position ihre vorher bestehende Reihenfolge bewahren. (Allgemein nennt man ein Sortierverfahren mit dieser manchmal wichtigen Eigenschaft "stabil".) Benutzen Sie zu diesem Zweck ein Hilfs-array, in das Sie die gefundenen Minima der Reihe nach eintragen (statt nach vorn zu tauschen) und zugleich im Quell-array als gelöscht markieren.
b) Wenden Sie min-sort auf ganze Zeilen an, wobei Zeile a[i] < Zeile a[j] ist, wenn beide bis zu einer Position k, 0 <= k < Zeilenlänge, übereinstimmen und dann a[i][k+1] < a[j][k+1] gilt.
Was ist der Aufwand (als Funktion von Zeilen-/Spaltenzahl) bei diesen Vorgehensweisen? Bauen Sie einen Zähler in das von Ihnen realisierte Verfahren ein!- Ihr Demo-Programm soll den Benutzer nach Zeilen-/Spaltenzahl fragen und das array mit Zufallszahlen besetzen.