schönes quicksort in C :D

Fluxx

Ach übrigens ein dicker Fehler ist mir in meinem ersten Posting unterlaufen:
Der bestmöglichste Overhead beträgt O(log(n)*n).
Der schlechteste, das habe ich zumindestens gelesen, O(n²). Kann ich aber nicht ganz nachvollziehen, meiner Meinung nach müsste der schlechteste Overhead O(n+n-1+n-2...1) sein.

@Drakos:
Natürlich hast du Recht, dass du beim Quicksort-Algo nie genau wissen kannst, wie schnell er läuft, was natürlich nachteilig ist. Aber soweit ich weiß, erreicht er doch durchschnittlich einen ähnlichen Overhead wie den bestmöglichen. Auch sonst kenne ich keinen besseren oder habe noch nie von einem besseren Sortieralgo gehört. Oder täusche ich mich da?

Und danke für die Verbesserung, das werde ich mir merken :).

Gruß,
Flux

Christoph

Drakos schrieb:

Aber um zur Frage zu kommen, da finde ich den Code von japro etwas sehr aufgebläht und sehe auch nicht ganz was insertion sort da drin macht(bitte erklären).

Quicksort arbeitet rekursiv nach dem Teile und Herrsche Prinzip. Die Teildaten werden immer kleiner. Ab einer gewissen Größe macht es aber keinen Sinn mehr, Quicksort zum Sortieren zu benutzen. Der Overhead durch die Rekursion ist größer als der Gewinn.
Deswegen ruft man ab einer bestimmten Schwelle Insertion Sort auf. Das macht aber auch nicht immer Sinn, da Insertion Sort ja ständig aufgerufen werden muss.
Daher ruft japro Insertion Sort erst ganz am Ende auf, da Insertion Sort sehr gut mit "etwas" sortierten Daten klarkommt.

threshold sollte aber AFAIK nicht 32 sein. Das ist zu groß. Gut sind Werte zwischen 5 und 25 (lt. "Algorithmen in C++").

japro

cd9000 schrieb:

threshold sollte aber AFAIK nicht 32 sein. Das ist zu groß. Gut sind Werte zwischen 5 und 25 (lt. "Algorithmen in C++").

ich habe damals als ich das gelesen mal ein quicksort in c++ implementiert und hatte dort mit 32 bessere ergbenisse als mit 5-25 wobei der unterschied von 32 bis 128 threshold so gut wie nicht messbar ist... ich führe das darauf zurück das in der zeit als der sedgewick rauskam noch andere prozessoren aktuell waren...

das meine variante etwas aufgeblächt rüberkommt liegt daran das ich so ziemlich alles wissen über optimierung von quicksort integriert hab das ich habe... diese variente hat wie schon von cd9000 schön erklärt diesen "insertionsortnachbrenner" natürlich median of 3 zur pivotierung und noch den schleifentrick der dafür sorgt dass:
1. weniger funktionsaufrufe getätigt werden
2. die rekurtsionstiefe nie log(N) übersteigt

(das einzige was ich kenne und was nicht drinn ist ist das umschalten auf heapsort falls die rekursion zu heftig wird... aber dann heisst es ja auch introsort und nicht mehr quicksort)

Fluxx schrieb:

...Der schlechteste, das habe ich zumindestens gelesen, O(n²). Kann ich aber nicht ganz nachvollziehen, meiner Meinung nach müsste der schlechteste Overhead O(n+n-1+n-2...1) sein.

hab das jetzt niccht nachüberlegt aber O(n+n-1+n-2...1) ist doch eigentlich das selbe wie O(n²/2) und das 1/2 lässt man weg weils ein konstanter faktor ist

@Drakos:
Natürlich hast du Recht, dass du beim Quicksort-Algo nie genau wissen kannst, wie schnell er läuft, was natürlich nachteilig ist. Aber soweit ich weiß, erreicht er doch durchschnittlich einen ähnlichen Overhead wie den bestmöglichen. Auch sonst kenne ich keinen besseren oder habe noch nie von einem besseren Sortieralgo gehört. Oder täusche ich mich da?

naja wie oben erwähnt es gibt introsort was aber eigentlich nichts anderes ist als eine anpassung von quicksort so das für teildateien die für quicksort ungünstig sind auf heapsort umgeschaltet wird welches auch im worstcase O(N log N) laufzeit hat. damit wird der katastrophale worstcase von quicksort quasi ausgegelichen.

Drakos

Wenn ich mich nicht täusche, ist aber heapsort generell nicht langsamer als quicksort, also im best case mind. gleich und im worst case schneller. der irre ich mich da?

japro

Drakos schrieb:

Wenn ich mich nicht täusche, ist aber heapsort generell nicht langsamer als quicksort, also im best case mind. gleich und im worst case schneller. der irre ich mich da?

prinzipiell ist es so das quicksort im bestcase optimal ist und im worstcase quadratisch (katastrophe).
heapsort ist im best- und wordstcase optimal... allerdings hat es eine längere innere schleife deshalb war es, soweit ich mich erinnern kann, bei meinen messungen im average case etwa um faktor 3 langsamer als quicksort.

Drakos

Ahja, das kann sein! Den avarage case hat ich nicht mehr im Kopf.
Aber mit Heapsort biste auf jeden Fall auf der sicheren Seite. Ich persönlich mag quicksort nicht sonderlich.

japro

wo ich schomal dabei bin:
heapsort

void downHeap(int A[], int pos, int size)
{
   int v = A[pos-1];
   while(pos <= size/2)
   {
      int pos2 = pos*2;
      if(pos2 < size && A[pos2-1] < A[pos2])
         ++pos2;
      if(v >= A[pos2-1])
         break;
      A[pos-1] = A[pos2-1];
      pos = pos2;
   }
   A[pos-1] = v;
}

void heapSort(int A[], int size)
{
   int i;
   for(i=size/2;i >= 1;--i)
      downHeap(A, i, size);
   while(size > 1)
   {
      swap(&A[0], &A[size-1]);
      downHeap(A, 1, --size);
   }

}

und introsort

void introSortLoop(int A[], int l, int r, int depth)
{
   while(r-l > threshold)
   {
      if(depth == 0)
      {
         heapSort(&A[l], r-l);
         --depth;
      }
      int p = partition(A, l, r);
      introSortLoop(A, l, p-1, depth);
      l = p+1;
   }
}

void introSort(int A[], int size)
{
   introSortLoop(A, 0, size-1, 2*pow(log(size),2));
   insertionSort(A, size);
}

Hallo,

Jeder Sortierlagorithmus, der auf Vergleichen beruht hat mindestens als Laufzeit O(n*log n). Dies ist die untere Schranke.

Mit Bucketsort, einteilen in Buckets (Fächer), kann wenn die Anzahl der
Buckets (Einteilkategorien) bekannt ist eine Laufzeit von O(2n) erreicht werden!!

japro

MisterX schrieb:

Hallo,

Jeder Sortierlagorithmus, der auf Vergleichen beruht hat mindestens als Laufzeit O(n*log n). Dies ist die untere Schranke.

Mit Bucketsort, einteilen in Buckets (Fächer), kann wenn die Anzahl der
Buckets (Einteilkategorien) bekannt ist eine Laufzeit von O(2n) erreicht werden!!

auch straight radix sort hat eine laufzeit von O(n)

aber solche algorithmen sind immer an bestimmte eigentschaften der schlüssel gebunden. bucketsort setzt voraus, dass alle schlüssel in einem bestimmten intervall sind und straight radix sort funktioniert nur auf integern. d.h. diese verfahren sind keine allzweckverfahren... und demnach nicht übbrall einsetzbar...

volkard

japro schrieb:

Mit Bucketsort, einteilen in Buckets (Fächer), kann wenn die Anzahl der
Buckets (Einteilkategorien) bekannt ist eine Laufzeit von O(2n) erreicht werden!!

lahm. bei geeigneter ordnungsrelation kenn ich einen mit O(2).

Griffin

mit digitalen sortierverfahren schaffste meist auch O(N) bei guter ordnungsrelation

japro

volkard schrieb:

japro schrieb:

Mit Bucketsort, einteilen in Buckets (Fächer), kann wenn die Anzahl der
Buckets (Einteilkategorien) bekannt ist eine Laufzeit von O(2n) erreicht werden!!

lahm. bei geeigneter ordnungsrelation kenn ich einen mit O(2).

^^seltsame art zu quoten...

Jester

Griffin schrieb:

mit digitalen sortierverfahren schaffste meist auch O(N) bei guter ordnungsrelation

Könntest Du ein solches mal zeigen?
Was ist eine gute ordnungsrelation?

a<=b für alle a,b? Dann schaffe ich O(1)!

Es ist nämlich prinzipiell nicht möglich den worst case O(nlog(n)) zu unterschreiten. Im Mittel kann man O(n) (vielleicht sogar besser hinkriegen).
Aber worst-case geht nicht besser als O(nlog(n)), wenn keine Informationen über die Schlüssel vorausgesetzt sind.

edit: besserem deutsch