Algorithmen[Prog1]

[Christian S.]

Mache ich auch so, bloß das Resultat stimmt trotzdem nicht . Es scheint bei kleinen Endrekursionen sehr viel Arbeit anzufallen, wobei mir aber nicht klar ist wieso (habe es auch mehrmals per Debugging durchgegangen).
Edit: Wie stark darf der Algorithmus denn modifiziert werden? Durch eine Modifikation am Anfang wird der bei mir DEUTLICH schneller, aber scheint weiterhin richtig zu sein, da keine Assertion failed (schon mehrere Versuche mit den Frameworks).
Edit 2: Meine Ergebnisse:
http://yfrog.com/5bpresortedp
http://yfrog.com/07randomip

[aaa1989]

Hallo,

Wollte fragen, ob man genau eine Methode presortedPrefixSort implementieren sollt mit genau den 2 Parametern wie auf dem Blatt (also sort(array a, int s)).
Ich wüsste dann nämlich nicht, wie man jeweils bei den Rekursionen, wo man z.B. (Sl & Ul) rekursiv sortieren muss, das machn soll. Die Methode sort(array, int s) kriegt ja nur den Array und eben s, was ja den index angibt bis wohin sortiert wurde... Mir fällt keine Lösung ein, wo man nicht ein neues Array erstellen muss um diesen dann zu übergeben (was dann doch nicht mehr "inplace" wäre, oder?).

[markusj]

Mache ich auch so, bloß das Resultat stimmt trotzdem nicht

Hey Christian, die Ergebnisse sehen doch ganz brauchbar aus! Ohne weitere Optimierungen sind das die Ergebnisse, die man von einer normalen Implementierung erwarten kann - insbesondere diese Peaks sind charakteristisch für den Algorithmus.

aaa1989:
Du solltest dich wohl noch etwas gründlicher mit Java auseinandersetzen - Arrays werden "by reference" übergeben, es wird also nur eine Referenz/ein Zeiger auf das Array bei der Rekursion weitergegeben, anstelle einer Kopie des Arrays.
Damit ist es aber auch erforderlich, die Grenzen des zu bearbeitenden Bereichs als Parameter zu übergeben und selbst aktiv zu überwachen, dass man nicht über diese Grenzen hinaus wandert.

mfG
Markus

[aaa1989]

Hmm, ich bin mir nicht sicher ob du verstanden hast was ich meine. Mir ist klar, dass nur ein Zeiger übergeben wird und keine Kopie. Meine Frage bestand darin, dass mir keine Lösung einfällt, falls man eben genau die Methode presortedPrefixSort(Array a, int s) mit diesen Parametern implementieren sollte. Ich kann ja bei der ganzen Rekursion immer nur ein Array a übergeben (zu eben der Methode presortedPrefixSort), und zusätzlich nur noch den Index s, der zeigt bis wohin das Array sortiert wurde. Wenn ich nun aber z.b. wie auf dem Blatt (Sl & Ul) sortieren müsste, müsste ich ja rekursiv eben diese Methode nochmal aufrufen, wo ich wiederum nur das Array a & eben den Index s übergeben kann. Nun weisst doch meine Rekursion nicht, dass es abbrechen sollte, falls es die Bereiche Sl & Ul schon sortiert hat?

Falls man aber auch noch mehr Parametern übrgeben kann, wäre es natürlich kein Problem... Ich hoffe, es war einigermaßen verständlich was ich meinte...

[salami]

@aaa
So wie ich das verstanden habe, soll der Pseudocode den Algorithmus nur sehr abstrakt darstellen. Man muss einfach das hinzufügen, was man noch benötigt.

[Chrisss]

aus aufgabenteil a) folgt eigentlich schon direkt, dass die methodensignatur eben nicht die des pseudo-codes sein soll/kann ^^
also da ruhig so machn dass es funktioniert

So hab das partitionieren jetzt nochmal ganz neu geschrieben sowie den index-kram naja.. keine endlos rekursion, funktioniert mit presorted wunderbar und der assertion-error kommt beim random-framework erst ab 32 stellen nunja bin mal gespannt ob das noch was wird aber immerhin wieder nen fortschritt^^
*EDIT:
GUT dass es so total durchschaubar is bei ner problemgröße von 32 mit all den rekursiven aufrufen nen fehler zu finden-.- omg wie soll ich den finden das wird ja ewig dauern^^^^
ich denke mal für einen nicht 100%ig korrekt funktionierenden algo gibts wohl mehr oder minder keine gnadenpunkte<.<
frag mich ja wie das bewertet wird, punkte gibts ja auf jedenfall wie im tut gesagt wurde für bestimmte optimierungen ...

[aaa1989]

Ok, vielen Dank, dann hats sich geklärt .

[n4zroth]

Hallöchen,
ich habe jetzt eine halbe Ewigkeit dran rum gewerkelt und der Algorithmus sortiert auch meiner Meinung nach richtig (

Code: Alles auswählen

int[] fu = new int[1000];

        Random rand = new Random();
        boolean noFail = true;

        while (noFail) {
            counter = 0;
            for (int i = 0; i < fu.length; i++) {
                fu[i] = rand.nextInt(100);
            }
    
            sort(fu, 0, fu.length - 1);
            
            for (int i : fu)    {
                System.out.print(i + " ");
            }
    
            for (int i = 1; i < fu.length; i++) {
                if (fu[i] < fu[i - 1]) {
                    System.out.println("Fail");
                    noFail = false;
                }
            }
        }

bricht auch nach langer Zeit nicht ab), aber das SortingFrameWorkRandom wirft mir einen AssertionError an den Kopf. Woher kann das kommen?

Edit: Oh Crap es bricht doch ab, sorry.
Edit2: Wenn ich es aus Eclipse heraus aufrufe, bricht die Schleife nach 2 Minuten nicht ab. Rufe ich es aber aus cmd heraus auf gibt es direkt beim 2. Array nen Fail aus. Weiß jemand woran das liegen kann? *help*
Update: So, die Ursache für den Fehler habe ich gefunden. Ich habe ein 64 Bit Betriebssystem, und habe automatisch auch aus der Konsole mit der 64 Bit Version vom JDK/JRE getestet. Da Eclipse aber nur die 32 Bit Version mag, musste ich vor langer Zeit ein separates 32 Bit JRE im Eclipse Ordner anlegen. Mit diesem hat Eclipse getestet. Wenn ich es damit teste, funktioniert es auch.
Die Frage ist nun: Was mache ich? Ist mein Algorithmus nun korrekt oder nicht? Und wie kann 32/64 Bit die Korrektheit beeinflussen?

[Enkidu]

Hi, irgendwie komisch der algorithmus hat uns ne ganze weile kopfzerbrechen bereitet. heute hab ich dann eine einzige optimierung gemacht, die alle probleme auf einen schlag gelöst hat (wir brauchen nur noch zwei rekursive aufrufe) und haben jetzt eine unglaubliche performance, aber ich bezweifle, dass es immer noch legal ist, da wir jetzt echt einen ganzen batzen aus dem algorithmus rausgeworfen haben. (z.b. dieses P)
Presorted: [img=http://img530.imageshack.us/img530/7468 ... ted.th.png]
Random:[img=http://img132.imageshack.us/img132/854/randomj.th.png]
OldPresorted:[img=http://img30.imageshack.us/img30/2916/o ... ted.th.png]
OldRandom:[img=http://img530.imageshack.us/img530/3086 ... dom.th.png]

[salami]

Hallo Enkidu
Das wird so schnell sortiert?
Im Ilias steht, dass man optimieren kann wie viel man will, solange der eigentliche Algorithmus noch ersichtlich ist (und verwendet wird) und die Optimierung nicht nur gemacht wurde, um sich die Arbeit zu erleichtern.

Das p gehört denk ich schon zum Algorithmus, weiß nicht ob es erlaubt ist, das einfach wegzulassen.
Hast du den Algorithmus auch mit Assertions getestet? Und wieso ist Quicksort schneller als JDK-Quicksort?