Algorithmen[Prog1]
Re: Algorithmen[Prog1]
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.
InsertionSort habe ich dann erst am Ende eingebaut, was aber, zumindest bei mir, nicht viel gebracht hat.
-
- Administrator
- Beiträge: 383
- Registriert: Do 23. Okt 2008, 20:16
- Wohnort: Karlsruhe
- Kontaktdaten:
Re: Algorithmen[Prog1]
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?
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?
-
- Administrator
- Beiträge: 383
- Registriert: Do 23. Okt 2008, 20:16
- Wohnort: Karlsruhe
- Kontaktdaten:
Re: Algorithmen[Prog1]
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
hat vllt noch jemand nen tipp oder meint ihr das meine laufzeiten so ok sind?
presorted
random
Re: Algorithmen[Prog1]
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.
Ob das s erweitert werden kann kontrolliere ich dann danach.
-
- Beiträge: 3
- Registriert: Di 28. Okt 2008, 23:09
Re: Algorithmen[Prog1]
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 ?
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 ?
Re: Algorithmen[Prog1]
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.
Das s muss dann entweder rausgefunden werden, oder man benutzt einfach s=1 und lässt es danach wachsen.
-
- Administrator
- Beiträge: 383
- Registriert: Do 23. Okt 2008, 20:16
- Wohnort: Karlsruhe
- Kontaktdaten:
Re: Algorithmen[Prog1]
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
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
-
- Beiträge: 3
- Registriert: Di 28. Okt 2008, 23:09
Re: Algorithmen[Prog1]
presortedPrefixSort(int a[],int s) hat folgende Parameter die übergeben werden ? Laut Aufgaben Stellung im Pseudocode
-
- Administrator
- Beiträge: 383
- Registriert: Do 23. Okt 2008, 20:16
- Wohnort: Karlsruhe
- Kontaktdaten:
Re: Algorithmen[Prog1]
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