Algorithmen[Prog1]

[salami]

Hallo,
wie schnell ist denn euer Algorithmus?
Ich habe gerade den Algorithmus fertig geschrieben und frage mich, wie schnell der Algorithmus eigentlich sein soll.
Meiner arbeitet in-place und funktioniert soweit auch (getestet auf vielen kleinen Arrays). Das SortingFramework (Random) rechnet jetzt aber schon gefühlte 10 Minuten ohne Ergebnis.
Dauert das bei euch auch so lange, oder ist meine implementierung einfach nur zu schlecht?

[markusj]

Auf einem T7200 (Core 2 Duo mit 2*2Ghz) braucht der Benchmark bei mir ungefähr ne Minute, vielleicht auch zwei ...
Und wie schnell mein Algorithmus ist: Im Schnitt zwischen dem mitgelieferten Quicksort und dem JDK-Quicksort.

mfG
Markus

[Nidan]

Ich brauche auf einem eee 901 1 bis 2 Minuten abhängig von aktivierten Assertions

allerdings ist die Laufzeit bei zufälligen Werten "interessant"

sortiert
zufällig

[salami]

Danke, habe gesehen, dass ich einen Fehler habe. Große Bereiche des Arrays wurden öfters sortiert, weil ich einen falschen Index übergeben hatte.

[jcdmb]

Leute, es gibt etwas in der Aufgabestellung die ich nicht verstanden habe: was ist der Zusammenhang zw. sort und presortedPrefixSort? Danke!

[salami]

@jcdmb
Schau mal in der Quicksort-Datei, dort sind auch 2 ähnliche Funktionen. Die eine ruft die andere einfach mit den richtigen Parametern auf.

Nochmal zum Graphen:
Soll es so "wellig" sein wie bei Nidan? Bei mir sieht es so aus:
http://i41.tinypic.com/16bd2k8.jpg

[markusj]

Nidan: Meiner ist auch recht "wellig", analog zu dir gibt es dort ein Dreiecksmuster dass ziemlich genau periodisch zum Exponenten modulo 4 ist.
salami: Hey, tolle Implementierung, so ähnlich sehen meine Ergebnisse auch aus.

mfG
Markus

[SLS]

Hier auch meine Ergebnisse Pro Test etwa 20 Sekunden auf Intel Core 2 Duo T5750 @ 2.0 GHz

Ich verstehe nur nicht, warum QuickSort sich so seltsam verhält bei mir im Vergleich zu den anderen Bildern im Forum

Presorted
Random

Nach einer kleiner Optimierung (vor der eigentlichen Bearbeitung, den Argumenten s so viel wachsen lassen wie möglich). Ich werde meinen Tutor fragen, ob das erlaubt ist (weil es ja abweicht von der Aufgabenstellung).

Presorted Optimized
Random Optimized

Ich kann mich nur wundern wie salami es "ganz unter" QuickSort im zufälligen Fall gebracht hat Vielleicht fällt mir gerade nicht ein, wie man die Wellenberge unterdrücken kann...

Habt ihr (und sollen wir) mit anderen Werten für p experimentieret?

[salami]

Nachdem ich meinen Algorithmus weiter "optimiert" habe, habe ich jetzt auch diese Wellenmuster drin.
Leider habe ich kein Backup gemacht, so dass ich jetzt nicht mehr zurück zum anderen Algo komme.

Egal. Die Wellenmuster kommen [bei mir] so zustande, dass an diesen Stellen sr viel größer ist als ul. Deshalb müssen mehr Kopieroperationen ausgeführt werden, was zu längeren Laufzeiten führt.

Hier mein Algo jetzt:
http://i44.tinypic.com/1zfs9d1.png

Da bei Mergesort hat Java wohl gerade einen Cache geleert oder gefüllt. Anders kann ich mir diese Ausreißer nicht erklären. Die treten immer wieder mal bei verschiedenen Algorithmen auf.

PS: Das mit dem s erhöhen habe ich auch.

[Christian S.]

Hat mir jemand einen Tipp wie ich s_r und u_l möglichst effizient vertauschen kann, wenn in u_l weniger Elemente als in s_r enthalten sind? Danke.