2 dimensionales feld sortieren

[Da_Hui]

hab eine schleife geschrieben, die ein zweidimensionales feld aufsteigend sortieren soll, leider hab ich irgendwo einen denkfehler drinnen und diesen bis jetzt nicht gefunden

die schleife sieht wie folgt aus (es handelt sich um java, sollte aber egal sein, da es sich nur um einen denkfehler handeln kann)


int i=0,j=0;
int min = feld[0][0];
int hilf;


for (i = 0; i < feld.length; i++) {
for (j = 0; j < feld[0].length; j++) {
for (int zeile = i; zeile < feld.length; zeile++) {
for (int spalte = j; spalte < feld[0].length; spalte++) {
if (feld[zeile][spalte] < min) {
min = feld[zeile][spalte];
hilf=feld[i][j];
feld[i][j]=min;
feld[zeile][spalte]=hilf;

}
}
}
}
}


wenn mir jemand helfen könnte wäre es sehr nett ;)

mfg Da_Hui

[Trap]

Was heißt "ein 2 dimensionales Feld sortieren"? Wann ist ein 2 dimensionales Feld für dich sortiert/nicht sortiert?

Welcher Sortieralgorithmus benutzt du?

[Da_Hui]

algorithmus selber schreiben, und ja sortieren is relativ .....

eigentlich egal wie es geht um einen sinvollen zugriff....

fürs erste besteht das feld aus integer zahlen die nach der größe sortiert werden sollen.
zuerst die kleinste zahl (links oben also feld[0][0]) bis zu größten.

später will ich sie nach teilbarkeit sortieren, aber dass is nur ein eigener algorithmus in der abfrage, leider ist schon in der schleife ein fehler, deshalb kann ich auch nicht weiterarbeiten.

und eine fertige sort funktion will ich nicht verwenden, da ich gerne änderungen vornehmen können würde......

deshalb versuchen ich eine schleife zu schreiben die jedes feld überprüft und dann in dass umspeichert


mfg Da_Hui

[Monger]

Was heißt "ein 2 dimensionales Feld sortieren"? Wann ist ein 2 dimensionales Feld für dich sortiert/nicht sortiert?

Gute Frage. Ein zweidimensionales Feld kann man logischerweise nicht auf einer Dimension sortieren, zumindest nicht ohne bestimmte Annahmen...


Welcher Sortieralgorithmus benutzt du?

Bubble Sort, siehst du doch! :)

Was natürlich unter Java ein echtes Verbrechen ist. Einfach das Comparable Interface implementieren, und gut ist. Reduziert den Code dramatisch, und macht die ganze Sache nicht nur übersichtlicher, sondern auch schneller.


Noch einmal: einen Bubble Sort selbst zu schreiben, ist (obwohl er nur ein paar Zeilen braucht) eine wirklich dämliche Idee!

Wie du selbst erkannt hast, sollte die Art der Datenstruktur nix mit der Sortierung zu tun haben. Du musst also an der Struktur arbeiten, nicht an der Sortierung.

[Trap]

Bubble Sort, siehst du doch! :)
Normalerweise schreibt man bubble sort mit ner while-schleife ganz außen und ich bin zu faul das ganze im Detail zu analysieren. Ich würde auf ein selection sort tippen.

Ich hab schon mal ein selection sort in Java geschrieben weil ich 2 Arrays aus eingebauten Datentypen gleich umsortieren wollte und keine Objekte drauß machen wollte.

[Da_Hui]

^^
es is richtig, dass es sinnlos ist, aber ich werde schon einen grund haben es selbst zu tippen ;)
ich weiß wie ich eine fertige sort funktion verwende, und ich will zur zeit keinen fertigen algorithmus sondern etwas ausprobieren, deshalb habe ich auch gefragt ob mir jemand helfen kann den fehler zu finden und nicht ob ich eine fertige sort methode ferwenden soll oder nicht ;)

sry falls sich dass wie kritik anhört, aber du musst zugeben, dass du mir damit nicht wirklich hilfst.

falls ich zum beispiel ein feld konstant lassen will, dass nicht in den sortiervorgang einbezogen wird, ist es leichter wenn man i, und j mit einer if afrage überprüfen kann, da ich keine sort funktion auswendig weiß bei der man parameter übergeben kann mit der ein einzelnes feld von der sortierung ausgeschlossen wird .......

nja wäre nett wenn mir jemand helfen könnte ......

mfg Da_Hui

[Trap]

Es kann dir nur jemand helfen wenn du sagst was deine Funktion genau machen soll.

Man kann 2-d Felder mindestens auf 10 verschiedene Arten sortieren, welche davon hättest du gerne?

[Da_Hui]

mein problem ist, wenn ich bubble sort verwende wie ich das letzt deld der ersten zeile letzen spalte mit dem ersten der nächsten zeile erste spalte vergleiche

bsp:
feld:

1 2 45 3
0 4 3 7
8 9 10 6

nach dem sortieren
0 1 2 3
3 4 6 7
8 9 10 45

also die kleinste links oben die größte rechts unten

hoffe es is eingermaßen klar ;)

mfg Da_Hui

[Da_Hui]

ok mein erster satz war müll ;)
sry

mein problem ist, wenn ich bubble sort verwende wie ich das "letzt feld" der "zeile" mit dem ersten feld der nächsten zeile vergleiche

so sollte es heißen...

[Da_Hui]

habs jetzt so gelöst, dass ich einfach, dass gesamte 2-d feld in einer "wurscht" in ein 1-d schreibe, dieses mit bubble sort sortiere und dann wieder zurückschreibe ;)

ich weiß dass das wohl eher ne pfuscher methode is, aber mir ist leider keine elegantere lösung eingefallen ^^

aber hat sich damit erledigt ......

mfg Da_Hui

[Monger]

sry falls sich dass wie kritik anhört, aber du musst zugeben, dass du mir damit nicht wirklich hilfst.

Ok, hast Recht.

Was deinen Code angeht:


min = feld[zeile][spalte];
feld[i][j]=min;
hilf=feld[i][j];
feld[zeile][spalte]=hilf;


Du schmeißt hier verschiedene Indizes durcheinander. Bist du sicher dass das richtig ist?
Das klassische BubbleSort sieht ja im Kern so aus:

hilf = feld[i];
feld[i] = feld[i+1];
feld[i+1] = hilf;


Das Problem hier ist, dass du zwei Probleme miteinander vermischst, die erstmal so nix miteinander zu tun haben. Der eine Teil (nämlich deine beiden äußeren Schleifen) machen (von der Idee her) aus deinem zweidimensionalen Array ein fortlaufendes, lineares Array. Darin eingebettet ist dein Bubble Sort.

An deiner Stelle würde ich beide Sachen trennen - zumindest durch zwei Methoden. Das gibt dir auch später die Chance, beide Probleme getrennt zu betrachten und auch zu modifizieren.

An deiner Stelle würde ich es also so machen:

- Dein zweidimensionales Array nehmen, und in ein eindimensionales Feld gleicher Größe einsortieren.

- das eindimensionale Feld sortieren.

- das eindimensionale Feld wieder in ein zweidimensionales Feld gleichen Maßes wie vorher einsortieren.


Ich sags aber nochmal: im Prinzip hast du hier zwei Probleme die nix miteinander zu tun haben, und die sich beide sauber lösen lassen:

- eigene sortierbare Datenstruktur bilden, indem man das List Interface implementiert
- Falls nötig, für die enthaltenen Elemente das Comparable Interface implementieren (was bei int unnötig ist, sofern es korrekt de- und geboxt wird)

[Matrix316]

Kopier einfach den zweidimensionalen Array in einen Eindimensionalen, sortiere den, und kopier wieder zurück. ;)

EDIT: Na toll, zwei Dumme ein Gedanke, sogar zur gleichen Zeit. ;)

[Monger]

EDIT: Na toll, zwei Dumme ein Gedanke, sogar zur gleichen Zeit. ;)

Ich war mindestens eine hundertstel Sekunde schneller! :D

[Gast]

Macht die Scheisse nicht zum Elefanten!

int arr[3][4] = {
{ 1, 2, 45, 3},
{ 0, 4, 3, 7},
{ 8, 9, 10, 6}
};
int *begin = &arr[0][0], *end = &arr[2][3];
sort(begin, end+1);

[Monger]

Macht die Scheisse nicht zum Elefanten!

int arr[3][4] = {
{ 1, 2, 45, 3},
{ 0, 4, 3, 7},
{ 8, 9, 10, 6}
};
int *begin = &arr[0][0], *end = &arr[2][3];
sort(begin, end+1);

Damit wirst du dir unter Java schwer tun. Dass das funktioniert, ist ja auch purer Zufall - weil halt zufällig alle Zahlen hintereinander im Speicher liegen. Allerspätestens wenn die Liste Referenzen enthält, würde das schon nicht mehr gehen.

[Gast]

Tut mir Leid hab den Code nur kurz angeschaut und ging von C++ aus, und da liegen die immer linear im Speicher.

[DocEW]

Also die Umkopiererei kannst du dir aber echt sparen...
Statt einer normalen Schleife in dem umkopierten Array mach sowas in der Art hier:
int feld[][] = new int[5][7];
int n,m,x,y;

n = feld.length;
m = feld[0].length;

for ( int i=0; i < n*m; i++) {
x = i % n;
y = i / n;
System.out.println("(" + x + ", " + y + "), ");
}