Algorithmen[Prog1]

[Thomas]

mittlerweile fuktioniert mein algorithmus aba meine laufzeit ist im vergleich zu den laufzeiten der andren algorithmen iwie extrem langsam. war der bei euch erst so schnell als ihr ihn mit insertionsort gedrückt habt oder von anfang an?
hab mal meine laufzeiten hochgeladen:
random
presorted

[salami]

Meiner war am Anfang auch langsam und quadratisch. Das lässt sich mit Optimierungen der Rekursionsaufrufe (s gleich übergeben) und Verbesserungen an der Partitionierung und beim Tausch von Ul/Sr verbessern.
InsertionSort habe ich dann erst am Ende eingebaut, was aber, zumindest bei mir, nicht viel gebracht hat.

[Thomas]

vom kurvenverlauf siehts iwie so aus wie bei den andren auch nur langsamer oder die andren eben deutlich schneller naja ich schau mal ob ichs noch gedrückt bekomme
Edit:
@ salami:
meinst du mit s übergeben eine überprüfung ob man s gleich erweitern kann? also zu schauen ob der sortierte bereich vergrößert werden kann?

[Thomas]

sry für den doppelpost wollte aba nochmal nachfragen was ihr zu den laufzeiten meint. ich erhöhre mittlerweile das s falls möglich. für presorted arrays macht das ganze auch ne erhebliche verbesserung bei zuälligen zahlenfolgen aba iwie nicht so wirklich.
hat vllt noch jemand nen tipp oder meint ihr das meine laufzeiten so ok sind?
presorted
random

[salami]

Mit s übergeben meine ich, dass für die Rekursion presortedPrefixSort(..) mit dem richtigen s aufgerufen wird und nicht sort(..).
Ob das s erweitert werden kann kontrolliere ich dann danach.

[SoulAssassinXT]

Hallo,
in der Aufgabenstellung steht das wir die void sort (int [] sequence, int i,int j) erweitern können , kann ich auch im Methoden Kopf eine zusätzliche Variable hinzufügen damit ich das s weiter geben kann an presortedPrefixSort ! In der Art sort (int [] sequence, int i,int j, int s){
presortedPrefixSort(int a[], int s);
}

Es handelt sich hierbei um ein Verständnisproblem !
presortedPrefixSort wird ja in sort aufgerufen ? verstehe ich das richtig ?

[salami]

Ich glaube nicht, dass man die Signatur von sort verändern darf, weil dann das Framework-Programm nicht mehr funktioniert.
Das s muss dann entweder rausgefunden werden, oder man benutzt einfach s=1 und lässt es danach wachsen.

[Thomas]

aso hab sowieso für die rekursion nur presortedPrefixSort benutzt und nicht sort, naja leider fällt mir nix mehr ein wie ich das ganze für zufallszahlen schneller machen könnte. vllt mach ich das ganze auch langsamer da ich zähle wieviele elemente in UR und wieviele in UL liegen. naja wenigstens ma die laufzeit der presorted arrays scheint jetzt so zu sein, wie sie der rest hier hat^^.
zum thema signatur von sort:
ich denke nicht dass man sort verändern soll/darf. kannst ja einfach mit s = 0 bzw s = 1 starten. und ja du musst in sort dann presortedPrefixSort aufrufen mit den passenden parametern

[SoulAssassinXT]

presortedPrefixSort(int a[],int s) hat folgende Parameter die übergeben werden ? Laut Aufgaben Stellung im Pseudocode

[Thomas]

die signatur von presortedPrefixSort musst du natürlich noch anpassen um zu wissen in welchem bereich du sortieren musst, ansonsten kannst du den algorithmus natürlich nicht umsetzen