zweidimensionales int Array sortieren

  • Themenstarter Themenstarter Gelöschtes Mitglied 70275
  • Beginndatum Beginndatum
G

Gelöschtes Mitglied 70275

Gast
Hallo, weiß jemand wie man ein zweidimensionales Array sortiert? Danke und viele Grüße.
 
Nach Datum sortieren Nach Zustimmungen sortieren
Ich meinte, daß es nicht wichtig ist, ob auf- oder absteigend. Das Array ist groß und ich bezweifle, daß ich vordefinierte Methoden aus dem Link oben verwenden kann. Meine Frage ist ernst gemeint.
 
Zustimmen 0
was würdest du tun wenn jemand bei dir zur tür rein kommt und sagt "ich will ein spiel haben, weis jemand wie das geht", was wäre deine reaktion? isn bischl mager die aussage 😉
 
Zustimmen 0
int [][] arr = new int[100000][300000]; (es ist unwichtig ob absteigend oder aufsteigend).
Angenommen es sind relative große int-Werte drin. Wie kann man dieses Array sortieren? Da es zweidimensional ist, habe ich ein Problem mit dem Sortieren.
Zuerst ein eindimensionales Array daraus zu machen funktioniert in meinem konkreten Fall nicht.
 
Zustimmen 0
... geht leider auch nicht, was ich gerade vor hatte. Hat nicht jemand zufällig einen Ansatz dafür - oder den Code?
 
Zustimmen 0
mach einfach einen einfachen sort.. bubble sort zb...wenn du das ende eines arrays gefunden hast springst du in die nächste array zeile bis du nicht mehr weiter springen kannst

oder du modifizierst den merge sort da du die "häufchen" für den merge sort mehr oder weniger schon hast wenn du jedes einzelne sortierst
 
Zustimmen 0
Nein - absolut nicht in einer DB.
Ja - das ist riesig. Habe die Werte willkürlich gewählt. Im kleinsten Falle komme ich auf etwa 80000 Einträge, und 30.000.000.000 ist auch die obere Grenze. Möglicherweise funktioniert es doch, sie in ein eindimensionales Array umzuschreiben und dann hätte ich nur 30.000.000.000 Vergleiche.
 
Zustimmen 0
Ich brauche eigentlich keine vollständige Sortierung - wenn das so ist. Ich brauche das Minimum/Maximum des Array-Eintrages.
 
Zustimmen 0
Ok, gehen wir von 100.000 MIPS aus (etwa einem 5 GHz Prozessor) und dass ein Vergleich/Tausch nur 10 Instruktionen braucht.
Länge: 30.000.000.000
Komplexität: (n log n)
(30.000.000.000 log 30.000.000.000) / 10.000.000.000 = 104,41 Sekunden

Also könntest du in unter 2 Minuten sortieren. Problematisch wird es erst bei noch mehr als 30 Milliarden Elementen.
 
Zustimmen 0
Gut, das wäre zwar nicht ok - ist aber so. Ich nehme den Weg über ein eindimensionales array und bestimme min/max. Hat jemand eine bessere Idee?
 
Zustimmen 0
Und halt zurück, letztendlich brauche ich die Vergleiche doch - ... . Also, wenn es funktionieren würde ein array in vier Teile zu zerlegen - ist eine gute Idee - dann bin ich auch damit zufrieden. Ich müßte dann alle Daten einlesen, das Array teilen und dann wieder zusammensetzen. Nun ja, wie geht sowas bei einem zweidimensionalen array?
Ich habe mal ein Beispiel für ein kleines Array gemacht. Wie kann ich das Minimum bestimmen, bzw. sortieren? Ich sollte es erst nochmals selber versuchen - aber bin nun schon die gesamte Zeit am lesen ...
Java: 
int[][] kleinesArr = {{1,7,3}, {1,2,3}, {9,2,3}, {1,2,3,4,5,6,7}, {1,2,3}, {1,2,3}};
 
Zustimmen 0
Ich habe gemerkt, daß bei > 30000 Einträgen eines eindimensionalen Arrays schon eine Exception entsteht. Also teilen muß ich dies ohnehin.
 
Zustimmen 0
Das Beispiel ist doof. Hier ein neues Beispiel:
Java: 
int d = 7; int o=8;       
int[][] klArr = new int[d][o];
        klArr[0][0] = 5 ;
        klArr[0][1] = 1 ;
        klArr[0][2] = 2 ;
        klArr[0][3] = 2 ;
        klArr[0][4] = 1 ;
        klArr[0][5] = 5 ;
        klArr[0][6] = 5 ;
        
        klArr[1][0] = 5 ;
        klArr[1][1] = 1 ;
        klArr[1][2] = 2 ;
        klArr[1][3] = 2 ;
        klArr[1][4] = 5 ;
        klArr[1][5] = 5 ;
        
        klArr[2][0] = 5 ;
        klArr[2][1] = 1 ;
        klArr[2][2] = 1 ;
        klArr[2][3] = 5 ;
        klArr[2][4] = 5 ;
        klArr[2][5] = 1 ;
        klArr[2][6] = 5 ;
        
        klArr[3][0] = 5 ;
        klArr[3][1] = 6 ;
        klArr[3][2] = 1 ;
        klArr[3][3] = 5 ;
        klArr[3][4] = 7 ;
        klArr[3][5] = 1 ;
        klArr[3][6] = 5 ;
        
        klArr[4][0] = 5 ;
        klArr[4][1] = 1 ;
        klArr[4][2] = 1 ;
        klArr[4][3] = 8 ;
        klArr[4][4] = 5 ;
        klArr[4][5] = 1 ;
        
        klArr[5][0] = 5 ;
        klArr[5][1] = 1 ;
        klArr[5][2] = 1 ;
        klArr[5][3] = 5 ;
        klArr[5][4] = 5 ;
        klArr[5][5] = 1 ;
 
Zustimmen 0
Danke an Alle für die vielen Beiträge. Ich versuche es und melde mich nochmals falls es nicht klappt. Brauche bestimmt zwei Tage, Bucket sort habe ich noch nie gehört.
 
Zustimmen 0
@jari auch vielen Dank fürs Mutmachen und daß zwei Minuten schnell sind - ein Quantencomputer ist nichts für diese riesige Ding hier - bin gerade echt am verzweifeln
 
Zustimmen 0
Ein Array zu sortieren ist simpel. Das Problem liegt in der 2. Dimension. Du hast bisher nicht beantwortet wann ein Unter-Array größer oder kleiner ist als ein anderes Unter-Array ist. Um mal mit einem Beispiel zu beginnen:
Java: 
public static void sortArray(int arr[][]) {
    Arrays.sort(arr, new Comparator<int[]>() {

        @Override
        public int compare(int[] o1, int[] o2) {
            return Integer.valueOf(o1[0]).compareTo(Integer.valueOf(o2[0]));
        }

    });
}
Per: Arrays.sort(...) kann man ein Array sortieren. In deinem Fall ist aber ein gesonderter Comparator notwendig, da die zu sortierenden Elemente auch Arrays sind und das Interface Comparable nicht implementieren. Also muss man selbst eine Methode zum Vergleich bereitstellen. Die Methode compare(int[] o1, int[] o2) vergleicht jetzt als Beispiel das erste Element jedes Unter-Arrays und sortiert das Ober-Array entsprechend. Du könntest natürlich auch jeden anderen Algorythmus anwenden, welchen du dir ausdenkst, z.B.: Quersumme über das Unter-Array.
 
Zustimmen 0
Hey Klasse, genau das brauche ich. Hätte nicht gedacht, daß meine Angaben nicht ausreichen. Sehe es nun aber ein. Jetzt habe ich eine Vorstellung, was ein zweidimensionales Array eigentlich ist.

Bei meinem Array haben alle Zeilen die gleiche Länge und alle Spalten haben die gleiche Länge. Spaltenlänge ist nicht gleich Zeilenlänge. Das macht es einfacher.
Ich denke mit einem Comparator wird es funktionieren.
Z. B. könnte ich mir vorstellen, zuerst die Spalten aufsteigend zu sortieren und dann einfach noch Zeile "0" aufsteigend zu sortieren. Das Minimum ist dann in a[0][0]. Dann würde ich die letzte Zeile aufsteigend sortieren und würde das Maximum in der letzten Zeile/Spalte erwarten.

Einen Comparator habe ich auch schon gefunden: https://www.java-forum.org/thema/2d-array-tabelle-alphabetisch-sortieren.42010/

Für mein zweites Teilproblem ist der Comparator auch geeignet. Welche Kriterien ich dann brauche muß ich einfach ausprobieren, kanns mir noch nicht vorstellen.
 
Zustimmen 0
Du hättest erwartet wie sortiert werden soll? Genau da hatte ich die Vorstellung, daß ein zweidimensionales Array wie in der Ausgabe von System.out.print ... ist, also wie ein eindimensionales mit Zeilenumbruch nach jeweils x Einträgen. Also, das sind eher arrays in einem array. Dann ist mir klar, dass man mehr Angaben braucht.
Eigentlich ist Sortieren oben auch nicht korrekt. Ich brauche ja nur den Vergleich. Ich probiere das jetzt aus, dann sehe ich ob es funktioniert - ohne Sortierung.
 
Zustimmen 0
suns hat gesagt.:
Ich brauche eigentlich keine vollständige Sortierung - wenn das so ist. Ich brauche das Minimum/Maximum des Array-Eintrages.
Zum Vergrößern anklicken....
Du willst nur das Minimum und Maximum im gesamten Array ermitteln? Warum willst du dann überhaupt sortieren? Iteriere doch einfach über alle Elemente, prüfe jeweils, ob das aktuell Betrachtete größer bzw. kleiner als das bisherige Maximum bzw. Minimum ist, merke es dir gegenfalls als neues Zwischenergebnis und du bist nach einem Durchlauf fertig.
 
Zustimmen 0
Ja, das ist das eine Teilproblem, für das andere brauche ich den Comparator. Siehe oben: Comparator (Sortierung ist eigentlich nicht richtig).
Es ist eine Frage der Performance, wie genau es gemacht werden wird. Ich muß möglicherweise nicht das gesamte Array durchlaufen.
 
Zuletzt bearbeitet von einem Moderator:
Zustimmen 0
🤔Es liegt bestimmt an mir, dass ich die Aufgabenstellung nicht begreife, denn einige andere haben es ja offenbar verstanden. Ich fasse mal meinen Kenntnisstand zusammen:

Es sollen mit Hilfe eines Sortieralgorithmus Minimum und Maximum aus einem großen zweidimensionalen Array ermittelt werden.
Minimum und Maximum reichen aber doch nicht ganz aus, sondern es wird zusätzlich noch etwas anders benötigt, das nicht definiert wird.
Die Sortierung braucht man aber doch nicht unbedingt, zumindest nicht vollständig und es besteht die Hoffnung nicht alle Elemente betrachten zu müssen.
Lösungsperspektiven können in der Überführung des 2D-Arrays in ein 1D-Array oder die logische Partitionierung in mehrere kleinere 2D-Arrays liegen.
Inzwischen ist auch klar, dass ein Comparator benötigt wird.
Nach einer Performanceoptimierung hat man dann die Lösung.
Die Kenntnis des zugehöriges Problem ist irrelevant.

Trifft das ungefähr den Punkt?😉
 
Zustimmen 0
Es soll also von links nach rechts aufsteigend sortiert werden und danach von oben nach unten anhand der ersten Spalte, richtig?
Dann wäre garantiert das kleineste Element links oben (sonst aber ist nichts garantiert).
 
Zuletzt bearbeitet:
Zustimmen 0

Aktuelle Jobs

Neue Themen

Ähnliche Themen

Übergabe von Werten (zweidimensionales Array) aus einer Methode an zweidimensionales Array in main()
Antworten: 3
Methode drawOval(int,int,int,int) von graphics
Antworten: 4
Verständnis-Problem repaint(int x,int y,int width,int height)
Antworten: 3
erste spalte eines zweidimensionales Array sortieren ??!!
Antworten: 2
Zweidimensionales Array sortieren, Häufigkeit ermitteln
Antworten: 22

Zurück
Oben