Sortieralgorithmus mit Rekursion funktioniert nicht

[GastXY]

Hallo, habe Probleme bei folgender Aufgabe:

Aufgabe 8.3 (20 Punkte)
Der Sortieralgorithmus Triple Sort arbeitet nach folgendem Prinzip:

1. Sortiere die vorderen zwei Drittel der Folge
2. Sortiere die hinteren zwei Drittel der Folge
3. Sortiere die vorderen zwei Drittel der Folge

Das Sortieren der Teilfolgen erfolgt jeweils rekursiv, zweielementige Folgen werden durch einfachen Vergleich der beiden Elemente sortiert. Einelementige Folgen sind bereits sortiert.

Implementieren Sie analog zur Klasse QuickSort eine Klasse TripleSort, die zwei sort-Methoden enthält: Eine private Methode, die nur in der Klasse TripleSort rekursiv aufgerufen wird und die Grenzen des aktuell betrachteten Array-Bereiches enthält und eine öffentliche Methode, die vom Benutzer aufgerufen werden kann und die private Methode initial aufruft.

Implementieren Sie außerdem eine Klasse TripleSortTest, mit der Sie die Methode testen können.

Hinweis: Der TripleSort operiert analog zum QuickSort direkt auf dem übergebenen Array.

Meine Methode sieht bislang so aus:

public class TripleSort{
    public static void sort(int [] a){
        int i = 0;                                       //Anfang vordere Zwei-Drittel
        int j = (a.length/3)*2;                              //Ende vordere Zwei-Drittel
        int m = (a.length/3);                               //Anfang hintere Zwei-Drittel
        int n = a.length;                                   //Ende hintere Zwei-Drittel    
        triplesort (a,i,j,m,n);
    }
    
    private static void triplesort(int []a, int i,int j, int m, int n){
       if (j-i<2){
            if (a[i]>a[j]){
                int tmp = a[i];
                a[i]=a[j];
                a[j]=tmp;
            }
        }
        if (n-m<2){
            if (a[m]>a[n]){
                int tmp= a[m];
                a[m]=a[n];
                a[n]=tmp;
            }
        }
        j=(j/3)*2;
        m=(m/2)*3;
        while((j-i>1) || (n-m>1))triplesort(a,i,j,m,n);
        
         
    }
}

wenn ich das Testprogramm starte kommt 1000mal die meldung:
"at TripleSort.triplesort(TripleSort.java:36)"

was kann ich tun?

MfG

 

[frapo]

Wie sieht denn dein Testprogramm aus? Mir scheint übrigens als sei die Fehlermeldung nicht komplett.

 

[GastXY]

import AlgoTools.IO;
public class TripleSortTest{
    public static void main(String [] argv){
    int[]a;
    IO.println();
    a= IO.readInts("Bitte Zahlenfolge");
    TripleSort.sort(a);
    for (int i = 0;i<a.length;i++)IO.println (" " + a[i]);
    IO.println();
    }
}

Das ist das Testprogramm.

Die Fehlermeldung ist so lang,bzw dieser satz wiederholt sich so häufig, dass das Terminal den oberen teil nicht mehr gespeichert hat ^^

 

[Gast]

hmm, hab jetzt n= a.length-1, was ja sinn macht. nun kommt die fehlermeldung zwar nicht mehr, aber das programm hängt in ner endlosschleife...

 

[Guest]

oh mein gott, jett kommts doch wieder, obwohl ich nur die bedingungen der letzten while-schleife geändert hab in:

while((j>i) || (n>m))

 

[mahe]

Es ist auf jeden Fall ein StackOverflow!

Ich werd mir mal ansehen wie das funktioniert (ich mag Sortieralgorithmen ).

 

[frapo]

Ich denke es hakt an folgender Zeile:

while((j-i>1) || (n-m>1))triplesort(a,i,j,m,n);

Wenn man diese auskommentiert, läuft das Programm zumindest durch.

 

[Gast]

ja, du hast recht, hab jetzt einfach mal die "zurückrollen" im terminal auf 200000 zeilen gestellt, nu seh ich die ganze fehlermeldung:

"Exception in thread "main" java.lang.StackOverflowError
at Triple...."

 

[Guest]

Ich denke es hakt an folgender Zeile:

while((j-i>1) || (n-m>1))triplesort(a,i,j,m,n);

Wenn man diese auskommentiert, läuft das Programm zumindest durch.

ja, nur das ist ja gerade der rekursive aufruf den das programm braucht, sonst sortiert es ja nichts ^^

 

[frapo]

ja, du hast recht, hab jetzt einfach mal die "zurückrollen" im terminal auf 200000 zeilen gestellt, nu seh ich die ganze fehlermeldung:

"Exception in thread "main" java.lang.StackOverflowError
at Triple...."

Das zeigt das mahe vorhin mit seiner Vermutung sehr richtig lag . Nun geht es also darum diesen StackOverflowError ausfindig zu machen, um ihn dann zu eliminieren.

 

[Gast]

Nur mal so nebenbei, sieht denn das Programm so aus als würde es wohl theoretisch sortieren?? ^^ habs gerad mit 2 zahlen im array und ohne die letzte whileschleife probiert, das funktioniert. ist ja schonmal etwas

 

[frapo]

Nur mal so nebenbei, sieht denn das Programm so aus als würde es wohl theoretisch sortieren?? ^^ habs gerad mit 2 zahlen im array und ohne die letzte whileschleife probiert, das funktioniert. ist ja schonmal etwas

Ich fürchte nicht. In meinem Array hab ich die Werte 1,5,23,44,3,7,32,2 und diese werden genau in dieser Reihenfolge am Ende ausgegeben.

 

[Gast]

das ist mir klar, weil du ja den rekursiven aufruf weglässt, dann macht er natürlich nix ^^

 

[nohfreak]

Tante Edith sagt:

Hier stand mal was, was hier nicht stehen sollte.

 

[Gast]

lol, danke ^^ ja, uos, tutor ist michael. und du?

 

[nohfreak]

Nicolas.

 

[mahe]

Soho, ich hab mir das jetzt mal etwas angesehen.

Du brauchst zwei Abbruchbedingungen (ein Element oder zwei Elemente), sowie die Sortierung der zwei Elemente.
Das hast Du fast.

Dann brauchst Du drei Rekursionsaufrufe. (Vordere zwei Drittel sortieren, hintere zwei Drittel und wieder vordere zwei Drittel).
Das hast Du gar nicht.

Deine Schleife kann sich nie wieder beenden wenn sie einmal durchlaufen wird. j, i, m und n ändern sich nämlich durch die Funktionsaufrufe nicht.
Schleifen sollte es aber sowieso nicht geben bei rekursiven Funktionen.

Leichter würdest Du es Dir außerdem machen, wenn Du der Funktion nicht die ganzen Drittel übergibts sondern nur Anfang und Ende des Bereichs den sie sortieren soll. Danach kann sie sich die Drittel selbst berechnen und diese durch einen weiteren Rekursionsaufruf sortieren lassen so die Abbruchbedingungen nicht erfüllt sind.

Und falls Du gar keine Lust mehr hast, kannst Du das probieren: (ich kenn euch sicher nicht )

class TripleSort {

	public static void sort(int[] a) {
		triplesort(a, 0, a.length);
	}

	private static void triplesort(int[] numbers, int start, int length) {
		if (length < 2) {
			return;
		} else if (length == 2) {
			if (numbers[start] > numbers[start+1]) {
				switchNr(numbers, start, start+1);
			}
			return;
		}

		int third = length/3;
		int twoThirds = length-third;
		
		triplesort(numbers, start, twoThirds);
		triplesort(numbers, start+third, twoThirds);
		triplesort(numbers, start, twoThirds);
	}

	private static void switchNr(int[] numbers, int a, int b) {
		int t = numbers[b];
		numbers[b] = numbers[a];
		numbers[a] = t;
	}
}

 

[nohfreak]

Hm. Hier spuken aber ganz schön viele rum.
Vielleicht ja auch dein Tutor. Also lieber aufpassen. ^^

 

[Gast]

hehe, hilfe is doch wohl erlaubt.

meins läuft nun auch, hatte vergessen, dass es ja 3 aufrufe sein müssen. danke nochmal an alle die geholfen haben

 

[0x7F800000]

@nohfreak: shalt mal die sichtbarkeit bei der rekursiven methoden auf private um, dann entspricht das eher der aufgabenstellung und den fall oben-unten=0 hättest du gesondert betrachten, und sofort das eine element wieder ausgeben können...

Aber das sind kleinigkeiten. Was mich eher interessiert: ein testprogramm hast du zwar geschrieben, aber hast du es auch getestet? :roll: versuch mal deine sortiermethode auf

int[] array={1,1,1,1,9,9,1,1,1,1};

loszulassen. Brauchst dich dann auch nicht zu wundern, dass da

[1, 1, 1, 1, 1, 1, 1, 9, 1, 9]

rauskommt.

Überleg dir nochmal genau, wo du was abrundest. Deine erste-drittel-zweite-drittel-erste-drittel mengen schneiden sich leider nicht immer vollständig.

Alles nur wegen diesen +-1 fehlern, übrigens. Warum hast du die obere grenze inklusive genommen? Was glaubst du, warum bei allen anderen Methoden in allen möglichen bibliotheken, ob in java oder c oder sonstwo, immer mit dem ersten und dem ersten nach dem letzten index gearbeitet wird, statt etwa mit dem letzten? Das ist schon nicht ohne guten grund so gemacht

 

[0x7F800000]

lösung mit der üblichen indizes-konvention wäre:

/** Triple-Sort größtenteils von nohfreak aus 
 * [url]http://www.java-forum.org/de/viewtopic.php?p=480750#480750[/url] 
 * geklaut und umindiziert 
 */
import java.util.Arrays;
public class TripleSort {

	public static void sort( int[] a ){
		sort(a, 0, a.length);
	}
	 
	private static void sort( int[] a, int unten, int oben ){
		if(oben - unten == 1) {
			// nur noch ein element da, nichts mehr zu tun
			return;
		}else if(oben-unten==2){
			// nur noch zwei elemente da, evtl vertauschen
			if(a[unten]>a[unten+1]){
				int temp = a[unten+1];
		    	a[unten+1] = a[unten];
		    	a[unten] = temp; 
			}
			return;
		}else{
			//rekursiv triple-sort auf teilarrays loslassen
			sort(a, unten, oben-(oben-unten)/3);
			sort(a, unten+(oben-unten)/3, oben);
			sort(a, unten, oben-(oben-unten)/3);
		}
	}
	
	// kleiner test
	public static void main(String[] args){
		int[] array={1,1,1,9,9,1,1,1};
		sort(array);
		System.out.println(Arrays.toString(array));
	}
}

ich kann jetzt immer noch nicht garantieren, dass meine Lösung fehlerfrei ist, aber zumindest konnte ich kein gegenbeispiel konstruieren, sollte eigentlich richtig sein.

 

[nohfreak]

Oi, danke dir Andrey, so hab ich da noch garnicht drüber nachgedacht.
Getestet hatte ich es schon, und die Zahlenfolgen, die ich getestet hatte haben auch funktioniert.

Ich werd deins auchnochmal ausprobieren. Auf jeden Fall nochmals danke für die Tips, wieder was gelernt.

 

[0x7F800000]

ich habe hier vor kurzem für eine hausuafgabe einen einfachen Algorithmus schreiben müssen, der eine Spezielle Art von Knoten in gerichteten Graphen suchen sollte. Hab mir kurz was überlegt, hab's implementiert, habe auch einen test geschrieben, hab's laufen lassen. Auf zufällig erstellten Graphen, mit jeweils paar hundert Knoten, hab den Test in einer schleife einige Millionen mal laufen lassen. Es hat millionenfach :!: den test bestanden. "Tolle Sache" dacht ich mir . Eine halbe Stunde später habe ich dann einen vergleichsweise mikroskopisch kleinen Graphen (grad mal 5-10 Knoten o.ä.) gefunden, bei dem der Algorithmus scheiterte :shock: . Musste mir dann nochmal was anderes überlegen, hat dann auch geklappt . Aber einfache tests, bei den massig zufällige versuchsanordnungen erstellt werden, sollte man auch mit vorsicht genießen, das war die Lehre aus der Geschichte^^

 

[Nicolas_mit_C]

1. schreibt man Nicolas mit c,
2. hast du dich durch die Klasse ToolBox verraten und musst nun bis zu deinem nächsten Testat zittern, weil ich ja nun weiß wer du bist,
3. fällt man bei plumpem Abschreiben einfach mal durch egal wie gut die anderen Aufgaben sind (durch die Klausur übrigens dann auch, weil man ja in den Testaten nichts gelernt hat ...),
4. würde ich doch arg darum bitten, Lösungen nicht im Netz zu verbreiten am Ende kommt noch jemand auf die Idee die Aufgabe aus der Wertung zu nehmen und dann siehts für die ein oder andere Gruppe schon arg eng aus mit Bestehen oder Durchfallen
und 5. gibt es keinen Tutor der Michael heißt.

Die besten Grüße,
Nicolas

 

[nohfreak]

Verdammt.

Da will mal einmal nett sein und jemandem was gutes tun,...

 

[0x7F800000]

Wenn man das Abschreiben verhindern wollte, müsste man auf der stelle alle unis mit nuklearwaffen plattmachen :lol: : wenn der Wille da ist, schreiben die Leute sowieso irgendwo ab, wenn nicht über das Forum hier, dann eben über irgendwelche instant-messenger oder sonstwie. Und nohfreak hat hier nichts abgeschrieben, sondern eher quasi-musterlösung geliefert, was ja wohl mehr als nur ein "guter ansatz" ist :toll: (ansonsten machen wir hier ja auch keine Hausaufgaben, zumindest nicht, ohne die Leute zuvor solange gequält zu haben, bis die selbst anfangen zu lernen )
Aber was die verbreitung von Lösungen im Internet geht, da muss ich zustimmen. Allerdings ist das imho eher harmlos, wenn das die Studenten machen. Übel wird's erst dann, wenn das die Profs machen, und zwar mit den alten Klausuraufgaben. Wenn die Profs die vorjahresklausur einfach abschreiben, dann kommen evtl. die leute, die Ahnung haben schlechter davon, als die leute, die sich einen haufen von sinnfreien "theoretischen fragen" und realitätsfernen buntstift-auf-papier-programmen aus alten Klausuren ins Hirn reingeprügelt haben, ohne irgendwas zu raffen :roll:. Da wird's so richtig unfair, das sorgt (bei mir zumindest) für extrem viel Frust.

 

[nohfreak]

Da hat er wohl Recht der Andrey. Ich hab ja nicht abgeschrieben, sondern wollte dem armen Kerl helfen, der da um Hilfe gebeten hat. Ist ja nicht gesagt, dass er das abschreibt, vielleicht ist er ja so weise daran evtl. zu erkennen, wo sein Fehler lag ( wobei anzumerken ist, dass meins ja offensichtlich auchnicht ganz fehlerfrei ist ^^ ).

Konnte nicht widerstehen, wo er da schon genau die Aufgabenstellung stumpf mitgepostet hat. :>