Algorithmen[Prog1]

[Misda]

Erreicht ihr die Laufzeiten eigentlich mit dem Delegieren an InsertionSort bei einer bestimmten Grenze? Oder was für Tricks gibts da?

[salami]

Achso, ja ich hab es auch so gemacht wie bei qSort. Allerdings hab ich es nicht 1:1 kopiert, sondern selbst gemacht, deshalb weiß ich nicht, ob das Original kompatibel ist.

@Misda
Ja, ich benutze ab einer bestimmten Grenze InsertionSort. Das bringt bei mir aber nur minimal was. Es kommt auch stark darauf an welche Grenze man benutzt.

[Misda]

Was für Grenzen meinst du?

[salami]

Z.B. InsertionSort benutzen wenn n <= 10. Dann ist 10 die Grenze.
Und mit der Grenze sollte man probieren welche die beste ist. Wenn die grenze zu groß ist, wird der Algorithmus langsamer und wenn sie zu tief ist macht es keinen Unterschied.
Ich finde das ganze macht allgemein kaum einen Unterschied. Man sollte lieber versuchen unnötige Schleifenaufrufe oder Rekursionen wegzukriegen.
Mein Algorithmus ist jetzt wieder vollständig unter Quicksort.

[elTybbq]

nunja mein partitionieren sieht so ähnlich aus wie das bei qSort wobei wie gesagt ich nicht sicher bin ob das korrekt funktioniert^^

1 zu 1 kannst du es nicht übernehmen, z.B kann es ja vorkommen, dass alle Elemente echt kleiner oder größer sind als das Pivot, was bei Quicksort nicht passieren kann. Wenn du den Fall nicht abfängst, läuft dir die Indexvariable evtl. aus dem Teilbereich raus, den du gerade untersuchst oder es gibt ne IndexOutOfBoundsExcpetion

[Chrisss]

selbstverständlich nicht 1 zu 1 ^^ aber gut dann sollte das so ungefähr hinkommen
ich denke ich mach die indices-geschichte einfach noch n 3. mal neu .. die nerven wirklich heftig

[Thomas]

zum Thema partitionieren:
ich habs auch so ähnlich gemacht wie quicksort:
und zwar hab ich zusätzlich noch ne abfrage eingebaut ob i oder j den anderen rand erreicht haben und breche die while schleife dann ab. außerdem swape ich nur bei i < j und führe die ganze schleife auch nur für i < j aus. wenn ich fertig bin mit der schleife muss ich aba noch einen problemfall abfangen und zwar wenn i = j nach dem swapen und dann a < pivot ist. ich stell den code mal rein, falls jemand nen fehler findet oder so da ich mir sicher bin dass da was nicht stimmt, da ich ja noch assertions bekomme.

PRIME_BBCODE_SPOILER_SHOW PRIME_BBCODE_SPOILER: auf Anzeigen klicken

Code: Alles auswählen

do {
			while (!abbruch & pivot > a[i]) {
				if (i < uRightEndIndex) {
					++i;
					++uLeftZaehler;
				} else {
					++uLeftZaehler;
					abbruch = true;
				}
		    }
			while (pivot < a[j] & !abbruch2) {
				if ( j > uLeftStartIndex) {
					--j;
				} else {
					abbruch2 = true;
				}
			}
			if (i < j) {
				swap(a, i, j);
				++i;
				--j;
				++uLeftZaehler;
			}
		} while(i < j);
		
		if (i == j & i != uLeftStartIndex & i != uRightEndIndex) {
			if (a[i] < pivot) {
				uLeftZaehler++;
			}

Edit: hab mittlerweile ein array gefunden bei dem nicht die richtige reihenfolge rauskommt find aba leider den fehler nicht denke mal uLeftZaehler zaehlt nicht richtig bei bestimmten fällen und deswegen wirds falsch, aber sicher bin ich mir nicht. wär toll wenn jemand ne bessere methode hätte um das zu zählen^^

[Christian S.]

Hey Thomas, habe scheinbar das selbe Problem. Könntest bitte das Array mal posten, dann könnte ich schauen ob bei mir der Fehler auch auftritt.
Edit: Okay, ich bin ein Depp. Hatte vergessen s wieder auf 1 zu setzen in der run-Methode XD.

[Christian S.]

Jetzt sollte er nur noch etwas schneller laufen ...

[wurstus]

hi,

ich mach das so, dass die if() keinen code enthält und der rest in einem else teil liegt.

also so ungefähr:

if(abruchsbed.) {
//nix tun
} else {
produziere mehr arbeit....
rekursion links bis grenze SR-UL
rekursion UL bis UR ende

rekursion von links bis rechts mit unsorted als sortierter bereich
}