Quicksort

Hallo,
ich habe mal eine Frag zu einem Teil einer Quicksort Implementierung:

do {
   while(a[li] < el) ++li;
   while(el < a[re]) --re;
   if(li<re) tausche (a[li],a[re]);
   if(li<=re) {++li; --re;}
}while(li<=re);
if(links < re) quicksort (a,links,re);
if(li < rechts) quicksort (a,li,rechts);

Wenn ich jetzt z.B. die Liste habe;

1234

und als Pivot Element 2 wähle. Sehe ich das richtig, dass die Funktion mit der Liste 34 ein 2. Mal aufgerufen wird? Also dass Quicksort nicht im Ersten Anlauf erkennt, ob eine Liste schon sortiert ist?

drakon

Ja. Quicksort ist in Θ(nlogn).

Skym0sh0

ich hab grade eifnach mal verscuht den quciksort zu optimieren indem ich einfach einen test anfangs mit rein genommen habe

und zwar geht der einfach alle zahlen durch, solange die aktuelle zahl kleienr als die nächste ist

bei kleinen mengen an zahlen 10-20 in der grössen ordnung ist de rgeschwindigkeitsvorteil sauhoch, ich schätze mal nur so 20 prozent oder sowas (also beis chon sortierten listen)
aber bei grossen mengen ist das eine bremse bis zum geht nicht mehr 1200% länger

voll hart

Bashar

Sinnvoller ist es wahrscheinlich, unterhalb einer bestimmten Arraygröße (welche, muss man experimentell ermitteln) einen anderen Sortieralgorithmus zu verwenden. Vielleicht einen, für den ein schon sortiertes Array der günstigste Fall ist.