WCM Forum - 2-Dimensionalen Array sortieren

WCM Forum (http://www.wcm.at/forum/index.php)

- Programmierung (http://www.wcm.at/forum/forumdisplay.php?f=17)

- - 2-Dimensionalen Array sortieren (http://www.wcm.at/forum/showthread.php?t=153033)

2-Dimensionalen Array sortieren

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.

Zitat:

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.

Bist du dir schon sicher, dass die Angabe richtig ist?
Ich versteh nicht ganz was du eigentlich genau machen willst, und wie man von den Zahlen {{8,1,-11,234} auf {{1,20,0,1111}, kommt. Außerdem ist die Klammersetzung falsch.

Zitat:

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}}

Erklärs doch bitte nochmal.(oder steh ich auf der Leitung...:confused: ;) )

Grüße,
Harri

Naja, dann gehts dir da so wie mir, ich steh nämlich auch, auf der Uni geht eh das gerücht um, dass die da einen fehler gemacht haben.
Weil wie man auf die zahlen kommt is mir auch rätselhaft gewesen.

ich als nicht student ;) denke mal:

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}}

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

und somit passt auch die klammernsetzung, man muss nur spaltenweise lesen, ned zeilenweise.

also sortierst du zuerst nach der ersten stelle, kriegst als erstes
1,20,0,1111
und dann die beiden mit 8 am Anfang (8,1,122,100 und 8,1,-11,234). Na dann sortierst die beiden nach der zweiten Stelle -> auch gleich, dann nach der dritten, und nachdem -11 vor 122 rauskommt kriegst eben dieses Ergebnis.

welche programmiersprache soll denn das ganze werden? vermutlich c oder? wie diese min verfahren allerdings funken - keine ahnung, ich würd einfach immer alle werte mit den nächsten vergleichen und danach sortieren - quasi bubblesort oder sowas

mfg Thomas

ok, ich probiers mal so.
das ganze soll in java sein.
kann mir hier wer von euch vielleicht ein codebeispiel geben?