zweidimensionales int Array sortieren

[Gelöschtes Mitglied 70275]

Hallo, weiß jemand wie man ein zweidimensionales Array sortiert? Danke und viele Grüße.

 

[Mart]

ja

 

[Gelöschtes Mitglied 70275]

... und wie geht das?

 

[Hansen_07]

Was genau willst du sortieren? Und wie? Absteigend? Aufsteigend?

Javainsel - Die Klasse Arrays zum Vergleichen, Füllen, Suchen und Sortieren nutzen

 

[Gelöschtes Mitglied 70275]

ist egal

 

[Hansen_07]

Alles klar. Danke für das Gespräch.

 

[Gelöschtes Mitglied 70275]

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.

 

[Mart]

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

 

[Gelöschtes Mitglied 70275]

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.

 

[Gelöschtes Mitglied 70275]

warte kurz, ich habe noch eine Idee. Wenn das nicht funktioniert, melde ich mich morgen nochmals.

 

[Gelöschtes Mitglied 70275]

... geht leider auch nicht, was ich gerade vor hatte. Hat nicht jemand zufällig einen Ansatz dafür - oder den Code?

 

[Mart]

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

 

[Gelöschtes Mitglied 70275]

versuche es - melde mich morgen. Danke.

 

[jari]

Nach welcher Spalte solll das Array sortiert werden?

 

[fhoffmann]

int [][] arr = new int[100000][300000];

Du hast also 30.000.000.000 Einträge in deinem Array. Wenn du ein Sortierverfahren benutzt, das O(n²) Vergleiche benötigt, so kommst du auf die Größenodnung von 900.000.000.000.000.000.000 Vergleichen - das kann eine Weile dauern!

 

[Mart]

man könnte auch altmodisch einer DB machen lassen

 

[jari]

man könnte auch altmodisch einer DB machen lassen

Hast du etwas geraucht?

 

[Mart]

Hast du etwas geraucht?

nein nur paar bier

+ 7 stunden laravel ... da weis ich net was schlimmer is XD

 

[Gelöschtes Mitglied 70275]

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.

 

[Gelöschtes Mitglied 70275]

laravel???

 

[Mart]

wofür brauchst du das riesen gerät überhaupt? eine spiel welt zu bauen?

das laravel ist unwichtig für dich

 

[Gelöschtes Mitglied 70275]

Mart - das ist wirkl. unwichtig! Und ich denke, es ist unwichtig für Dich wozu ich es brauche.

 

[Mart]

um das mal so "hinzustellen"

ein int hat 4 byte dh

30.000.000.000 * 4 = 120.000.000.000

das sind umgerechnet 111.76 Giga Byte... muss das denn sein?

 

[fhoffmann]

dann hätte ich nur 30.000.000.000 Vergleiche.

Die Anzahl der Vergleiche wächst mit dem Quadrat der Einträge - du hättest also doch 900.000.000.000.000.000.000 Vergleiche.

 

[Gelöschtes Mitglied 70275]

Warte mal, ich denke anders, denn ich brauche das Minimum und das Maximum.

 

[Mart]

bei 10000 vergleichen pro sekunde dauert es nur schlappe 25 000 000 000 000 stunden bis es fertig ist

 

[Gelöschtes Mitglied 70275]

Ich brauche eigentlich keine vollständige Sortierung - wenn das so ist. Ich brauche das Minimum/Maximum des Array-Eintrages.

 

[jari]

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.

 

[Gelöschtes Mitglied 70275]

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?

 

[fhoffmann]

Ich nehme den Weg über ein eindimensionales array

Warum das? Min und Max kannst du doch auch in einem zweidimensionalen Array bestimmen.

 

[Mart]

du bist bei deinen paar werten nur um schlappe

25.705.032.705

über den Int wertebereich drüber wenn du nur 1 array benutzt

 

[jari]

Gut, das wäre zwar nicht ok - ist aber so.

Wieso denn das? Ist doch noch relativ schnell. Die Frage ist was du mit wen Werten machen möchtest.

 

[Gelöschtes Mitglied 70275]

Ich finde nicht daß es schnell ist.

 

[Gelöschtes Mitglied 70275]

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

int[][] kleinesArr = {{1,7,3}, {1,2,3}, {9,2,3}, {1,2,3,4,5,6,7}, {1,2,3}, {1,2,3}};

 

[Gelöschtes Mitglied 70275]

Ich habe gemerkt, daß bei > 30000 Einträgen eines eindimensionalen Arrays schon eine Exception entsteht. Also teilen muß ich dies ohnehin.

 

[Gelöschtes Mitglied 70275]

Das Beispiel ist doof. Hier ein neues Beispiel:

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 ;

 

[Mart]

du kannst es mit dem bucket sort probieren insofern die werte in einem normalen bereich liegen

 

[jari]

Ich finde nicht daß es schnell ist.

Dann musst du eben auf einen Quantencomputer warten.

 

[Gelöschtes Mitglied 70275]

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.

 

[Gelöschtes Mitglied 70275]

@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

 

[fhoffmann]

Du hast aber schon die Bemerkung von @Mart (unter Nummer 23) gesehen, dass du über

111.76 Giga Byte.

Arbeitsspeicher benötigst.
Möglicherweise solltest du uns doch verraten, was du eigentlich machen willst, auch wenn du schreibst:

Und ich denke, es ist unwichtig für Dich wozu ich es brauche.

 

[jari]

Also, wenn es funktionieren würde ein array in vier Teile zu zerlegen

Ein zweidimensionales Array unterscheidet sich doch nur in der Adressierung von einem eindimensionalen. Du kannst also das 2d Array beibehalten und musst nur darauf richtig operieren.

Was und wie soll denn genau sortiert werden, jedes einzelne "Unterarray"?

 

[Oneixee5]

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:

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.

 

[Gelöschtes Mitglied 70275]

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.

 

[Mart]

Hätte nicht gedacht, daß meine Angaben nicht ausreichen.

???

 

[Gelöschtes Mitglied 70275]

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.

 

[Meniskusschaden]

Ich brauche eigentlich keine vollständige Sortierung - wenn das so ist. Ich brauche das Minimum/Maximum des Array-Eintrages.

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.

 

[Gelöschtes Mitglied 70275]

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.

 

[Meniskusschaden]

🤔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?

 

[Neumi5694]

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).