Rekursion endet nicht

[Bassking]

Hallo,

ich wollte einfach nur nen Quicksort programmieren, benutze Eclipse und
eigentlich wird das Array auch gut sortiert.
Kommt das Programm zur Abbruchbedingung der Rekursion springt es aber trotzdem wieder in die Rekursion zurück und ich blicke nicht ganz, warum. Das führt nämlich dazu, dass die Liste wieder unsortiert wird und schon beim Compilieren gestreikt wird.

public class haupt {

	public static void main(String[] args)
	{
	int feld[]={4,2,7,9,55,3,1,2,11,8};
	int pivotIndex = feld[feld.length/2];
	
	quicksorte(feld,0,9);
	for (int i=0; i<feld.length;i++)
	{
	System.out.println(feld[i]);
	}
	}

	public static int sortieren (int feld[], int left, int right, int pivot)
	{
	int pivotWert = feld[pivot];
	int tauschen = feld[right];
	feld[right]=feld[pivot];
	feld[pivot]=tauschen;
	int start = left;
	for (int i = 0; i<right; i++)
	{
	if (feld[i]<=pivotWert)
	{
	int tausch = feld[start];
	feld[start]=feld[i];
	feld[i]=tausch;
	start++;
	}
	}
	int tausch2 = feld[right];
	feld[right]=feld[start];
	feld[start]=tausch2;
	return start;
	}

	public static void quicksorte (int feld[], int left, int right)
	{
	if (right > left)
	{
	int PivotIndex=(right/2);
	int PivotNewIndex=sortieren(feld,left,right,PivotIndex);
	quicksorte(feld,left,PivotNewIndex-1);
	quicksorte(feld,PivotNewIndex+1,right);
	}
	
	}}

Danke für jeden Tip!

*Wildcard - Codetags eingefügt*

 

[solnze]

uih ohne code tags tun mir beim lesen die augen zu doll weh, sorry.

 

[SlaterB]

> Das führt nämlich dazu, dass die Liste wieder unsortiert wird und schon beim Compilieren gestreikt wird.

wenn das Programm schon 'beim Comilieren streikt'
(= nicht kompiliert?)
also nie läuft, wie kann es dann 'eigentlich[..] auch gut sortiert' werden?

----------

fange mit einem einfachen Array der Länge 2 oder 3 an,
und baue Ausgaben in dein Programm!
System.out.println hier, System.out.println da

verfolge zunächst mal nur oberflächlich, was als Pivot gewählt wird,
welche Indexe left, right,
und wie dann die rekursiven Aufrufe aussehen,

dann wirst du herausfinden, an welche Stelle sich nix tut -> Endlosschleife

--------

funktioniert natürlich nur, wenn das Programm schon läuft,
falls es Compiler-Fehler gibt: welche?

 

[Guest]

Das schöne an Eclipse ist, dass es Programme ausführt, obwohl sie in der Konsole mit javac nicht comiled werden können.
Das Programm läuft komplett durch, sortiert das ganze und wenn rechts nicht mehr > links ist, sollte es ja eigentlich aufhören mit dem rekursiven Aufrufen.
Rechts wird also irgendwann 0, das Feld ist schon schön sortiert (zu sehen im Debug Modus von eclipse) und links ist auch 0,
nun sprint das Programm über den Inhalt der If-Bedinung weg, dann aber wieder rein zum erneuten quicksort-Aufruf.
Da liegt das Problem.

 

[FelixB]

Das schöne an Eclipse ist, dass es Programme ausführt, obwohl sie in der Konsole mit javac nicht comiled werden können.

LOL

ein Programm, das nicht kompiliert werden kann, ist auch nciht ausfürhbar. Auch nicht von Eclipse. In so einem Fall wird die zuletzt kompilierte Version gestartet...

 

[Wildcard]

LOL

ein Programm, das nicht kompiliert werden kann, ist auch nciht ausfürhbar.

Nein, so stimmt das nicht. Siehe Scrapbook-Page...

 

[Roar]

eclipse kompiliert und führt auch programme aus, die fehler haben, fliegt nur zur laufzeit ein entsprechender error

 

[solnze]

eclipse kompiliert und führt auch programme aus, die fehler haben, fliegt nur zur laufzeit ein entsprechender error

und das auch nur wenn der teil des codes der einen fehler hatauch tatsaechlich ausgefuehrt wird mein ich.


wie dem auch sei, das aendert nichts daran dass basssking mit dem einfuegen von ein paar ausgaben einfach testen kann woran der fehler liegt, wenn die if bedingung uebersprungen werden soll dann darf sie nicht zutreffen, gib die werte einfach mal aus und guck wo da der fehler liegt.


edit: bloed formuliert

 

[Basskig]

naja, auf jeden Fall passieren die einzelnen Programmschritte und es werden Sachen auf der Konsole ausgegeben, so als würde man es schritt für schritt ausführen. Wichtiger wäre eigentlich, dass mir vielleicht mal jemand bei meinem Problem hilft, das wär sehr nett.

 

[SlaterB]

wenn rechts und links 0 sind und
if (right > left)
{
dennoch ausgeführt wird, tja dann kann man nix mehr machen


andererseits darf man ja stark vermuten, dass du dich irrst und Java doch funktioniert,
puh, Glück gehabt,

falls es dich glücklicher macht, dann ändere den Code in

System.out.println("vor if, right: "+right+", left: "+left);
if (right > left) 
{ 
    System.out.println("in if, right: "+right+", left: "+left);
...

und siehe da, du wirst nie die Ausgabe
in if, right: 0, left: 0
erhalten

---------

und noch ein Tipp: solange Compilerfehler da sind, sollte man diese beheben,
auch wenn Eclipse da zaubert

 

[bassking]

was für ein Post Tempo
Naja, die Sache ist die: die If bedingung (die in der quicksorte methode) soll ja am Ende übersprungen werden, das klappt ja auch und per Debug Modus sehe ich auch Variablen und Array die alle die passenden Werte haben. Trotzdem geht er am Ende des Programm, wo er eigentlich in die MainMethode zurücksollte, wieder in die quicksort rekursion rein.

 

[Guest]

der Compilerfehler entsteht ja erst danach. Weil er sich dann sozusagen out of stack sortiert^^

 

[SlaterB]

zu deinem ersten Folge-Post:
ach, das hattest du ja noch gar nicht erwähnt (ironisch)

wie auch immer, wenn du weiterhin irgendwas über deinen Debug-Modus erzählst,
dann kann ich nicht helfen,


System.out.println ist dein unbestechlicher Helfer,
funktioniert auf allen PCs der Welt gleich und findet jeden Fehler in solchen simplen Programmen millimetergenau

-------

zum zweiten:
Compilerfehler entstehen nie 'danach', du meinst dann vielleich eine Exception zur Laufzeit?

 

[Guest]

was ist verkehrt am Debug Modus?

Er geht eben Schritt für Schritt durch und an der berüchtigen if stelle
tritt eben genau der Fall ein, dass right 0 und left 0 ist.
Dann wird der weitere Teil übersprungen, aber trotzdem gehts vom übersprungenen wieder zurück.

Oder liegt es am Debugmodus? ich hab leider das ganze eben auf einem anderen Rechner, an den ich nicht rankomme, programmiert, wenn du sagst, debugmodus zeigt mir falsche variablenwerte an, probier ich das ganze, sobald ich kann, mit deiner Methode.

 

[SlaterB]

ich kann mir vorstellen, dass man beim DebugModus jede Menge komischer Sachen machen kann,
vielleicht gar zwischen 2 Breakpoints hin- und herspringen,

aber ist ja auch egal, wenn du damit hinkommst umso besser,
nur ich kann nicht nachvollziehen was du beim Debug falsch oder richtig machst,
daher helfen deine Ergebnisse dort nicht bei der Fehlersuche
(obwohl es gerne sehr leicht möglich wäre, damit den Fehler zu finden),

wenn du davon weggehst und System.out.println benutzt, die Ergebnisse anschaust und wichtige Stellen hier postest,
dann kann ich dir Schritt für Schritt sagen, wie du den Fehler immer weiter eingrenzt,
so dass du es das nächste Mal selber kannst,

da ist kein Können dabei, nur Fleiß

 

[Bassking]

So, das ende sieht nun so aus:

public static void quicksorte (int feld[], int left, int right)
   {
   if (right > left)
   {
   int PivotIndex=(right/2);
   int PivotNewIndex=sortieren(feld,left,right,PivotIndex);
   quicksorte(feld,left,PivotNewIndex-1);
   quicksorte(feld,PivotNewIndex+1,right);
   }
   System.out.println("geht");
   }}

Und die Konsole gibt folgendes heraus:

geht
geht
geht
geht
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
at quicks.sortieren(quicks.java:26)
at quicks.quicksorte(quicks.java:43)
at quicks.quicksorte(quicks.java:44)
at quicks.quicksorte(quicks.java:45)
at quicks.quicksorte(quicks.java:44)
at quicks.quicksorte(quicks.java:44)
at quicks.quicksorte(quicks.java:45)
at quicks.quicksorte(quicks.java:44)
at quicks.quicksorte(quicks.java:44)
at quicks.quicksorte(quicks.java:44)
at quicks.main(quicks.java:8)


Ich kann leider nicht nachvollziehen, warum er bis zum

 System.out.println("geht");

kommt, dann aber anscheinend doch wieder zurück zur rekursion geht.
Bitte helft mir

 

[SlaterB]

na nun konstruktiv weiter, Zeile 26 herausfinden,
davor eine Ausgabe welcher Index da benutzt wird (start ist 10)

woher kommt start?
quicksorte reicht das nur durch (Parameter left)

also der Aufrufer von quicksorte,
ich vermute die Zeile
quicksorte(feld,PivotNewIndex+1,right);
da ist vielleicht PivotNewIndex schon 9 (der letzte im Array)

zu testen indem du vor
quicksorte(feld,PivotNewIndex+1,right);
schreibst:
System.out.println("gleich Aufruf mit PivotNewIndex+1, PivotNewIndex ist: "+PivotNewIndex);
usw.

das leichteste der Welt..........,
keine halbe Sekunde Nachdenken nötig, nur schauen was das Programm macht,

 

[bassking]

Mein Problem ist ja aber eigentlich was anderes:
Sobald rechts 0 und links 0 ist MÜSSTE die Liste ja sortiert sein. Es soll ja danach gar nicht weitergehen.

 

[bassking]

public static void quicksorte (int feld[], int left, int right)
   {
   if (right > left)
   {
   int PivotIndex=(right/2);
   int PivotNewIndex=sortieren(feld,left,right,PivotIndex);
   //System.out.println(PivotNewIndex);
   quicksorte(feld,left,PivotNewIndex-1);
   quicksorte(feld,PivotNewIndex+1,right);
   }
   System.out.println("right=" +right+ "   left="+ left);
   for (int i = 0; i<feld.length;i++)
   System.out.println(feld[i]);
   }

Bei dieser Veränderung spuckt die Konsole aus:

right=0 left=0
1
2
2
3
4
7
8
9
11
55
right=1 left=2
1
2
2
3
4
7
8
9
11
55
right=1 left=0
1
2
2
3
4
7
8
9
11
55
right=3 left=3
7
8
4
2
2
11
3
9
1
55
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 10
at quicks.sortieren(quicks.java:27)
at quicks.quicksorte(quicks.java:44)
at quicks.quicksorte(quicks.java:46)
at quicks.quicksorte(quicks.java:47)
at quicks.quicksorte(quicks.java:46)
at quicks.quicksorte(quicks.java:46)
at quicks.quicksorte(quicks.java:47)
at quicks.quicksorte(quicks.java:46)
at quicks.quicksorte(quicks.java:46)
at quicks.quicksorte(quicks.java:46)
at quicks.main(quicks.java:8)


Warum springt er also wieder in die Rekursion, obwohl die Liste geordnet und die Abbruchbedingung erfüllt ist?

 

[SlaterB]

was meinst du denn? dass nach dem ersten 'geht' nix mehr passieren sollte?
nene, das scheint mir nicht so, obwohl ich mir den Algorithmus natürlich nicht ganz genau angeschaut habe,

aber warum hast du dann
quicksorte(feld,left,PivotNewIndex-1);
quicksorte(feld,PivotNewIndex+1,right);

zwei Aufrufe?
am Ende des ersten kommt ja schon das erste 'geht',
wozu dann noch den zweiten?

du solltest dann also erstmal überlegen, was du haben willst,
ich nehme stark an, dass da eine Menge 'geht' kommen müssen, bevor es zu Ende ist

 

[bassking]

Es sollte dann nichts mehr passieren, weil die Liste zu dem Zeitpunkt ja fertig sortiert ist.
Oder seh ich das falsch?

 

[SlaterB]

ja siehst du falsch nach meiner Meinung, habe ich das nicht geschrieben?
und frag nicht mich, was du daran falsch siehst/ wie das ablaufen soll

lies mein vorheriges Post noch einmal in Ruhe durch

und noch mal als Tipp: fange mit kleinem Array [4,3] an

 

[bassking]

hm. naja, finds trotzdem merkwürdig, warum die liste schon fertig sortiert ist, aber quicksort wird sich schon was dabei denken^^
ich probier weiter

 

[Guest]

for (int i = left; i<right; i++)

So, hier war i vorher immer gleich 0, das ist natürlich kappes, wie mir grade auffiel^^

 

[Guest]

int PivotIndex=((right+left)/2);

Hier hab ich vorher auch eine Unsinnige Angabe gemacht, der Pivot war dann teilweise nicht innerhalb der Links-Rechts-Spanne.
Jetzt funktionierts, danke für die Hilfe.[/quote]