schönes quicksort in C :D

[japro]

ich hab mal versucht ein möglichst sauberes quicksort in c zu schreiben (nur integer). wäre froh über verbesserungsvorschläge jeder art (algorithmus, stil usw.)

const int threshold = 32;

void swap(int *a, int *b)
{
   int xchg = *a;
   *a = *b;
   *b = xchg;
}

int* medianOfThree(int *a, int *b, int *c)
{
   if(*a < *b)
      if(*b < *c)
         return b;
      else if(*a < *c)
         return c;
      else
         return a;
   else
      if(*a < *c)
         return a;
      else if(*b < *c)
         return c;
      else
         return b;
}

int* minElement(int A[], int size)
{
   int i;
   int *min = &A[0];
   for(i=0;i<size;++i)
      if(A[i] < *min)
         min = &A[i];
   return min;
}

void insertionSort(int A[], int size)
{
   int i;
   swap(&A[0], minElement(A, threshold));
   for(i=2;i<size;++i)
   {
      int v = A[i], j = i-1;
      while(A[j] > v)
      { A[j+1] = A[j]; --j; }
      A[j+1] = v;
   }
}

int partition(int A[], int l, int r)
{
   swap(&A[l], medianOfThree(&A[l], &A[(r+l)/2], &A[r]));
   int v = A[l];
   int i = l+1;
   int j = r;

   for(;;)
   {
      while(A[i] < v)
         ++i;
      while(A[j] > v)
         --j;

      if(i >= j)
         break;

      swap(&A[i], &A[j]);
      ++i; --j;
   }
   swap(&A[j], &A[l]);
   return j;
}

void quickSortLoop(int A[], int l, int r)
{
   while(r-l > threshold)
   {
      int p = partition(A, l, r);
      if(p-l > r-p)
      {
         quickSortLoop(A, p+1, r);
         r = p-1;
      }
      else
      {
         quickSortLoop(A, l, p-1);
         l = p+1;
      }
   }
}

void quickSort(int A[], int size)
{
   quickSortLoop(A, 0, size-1);
   insertionSort(A, size);
}

[Fluxx]

japro schrieb:

int partition(int A[], int l, int r)
{
   //...
   int v = A[l];
  //...
}

Ich habe etwas Schwierigkeiten, den Code vollständig zu verstehen, da ich bisher noch nie etwas mit Insertionsort, sondern nur mit reinem Quicksort zu tun hatte. Dies ist aber natürlich mein, nicht dein Fehler ;).
Wenn ich aber richtig verstanden habe, dass das oben zitierte Argument int l die untere Grenze deiner "Partition" ist, und v der Refernzwert, ist die oben gepostete Zeile eher schlecht, da man bei einem bereits vorsortierten Array den maximalen Overhead von O(log(n)*n) hätte. Besser ist:

int v=A[(l+r)/2];

[Fluxx]

Ahh ich sehe grad, dass mein Kommentar ein SChnellschuss war ;). Hab die beiden Codezeilen drüber und drunter nicht genau betrachtet.
Sorry meinerseits, alles super

[Fluxx]

Wobei ich aber dennoch nicht verstehe, was ganz genau in deiner Funktion abläuft. Wie gesagt, das mag an mir liegen.

Ich habe bisher Quicksort immer folgendermaßen verwirklicht(nur ein aus dem Kontext gebrochenes Codebeispiel, denke aber zeigt den Ansatz):

void Liste::Quicksort(vector<Tnode*>& Vec, int hi, int lo){
	int i=lo;
	int j=hi;

	string x=Vec[(hi+lo)/2]->Name; //Referenzwert

	while(i<=j){
		while(Vec[i]->Name<x) ++i;
		while(Vec[j]->Name>x) --j;

		if(i<=j){
			Tnode* Temp=Vec[i];
			Vec[i]=Vec[j];
			Vec[j]=Temp;

			++i; --j;
		}
	}

	//Rekursion
	if(i<hi)
		Quicksort(Vec,hi,i);
	if(j>lo)
		Quicksort(Vec,j,lo);
}

Find ich irgendwie kürzer und verständlicher.

Oder ist dein Code schneller/sicherer?
KLäre mich auf

[Drakos]

string x=Vec[(hi+lo)/2]->Name; //Referenzwert

Ist zwar im Durchschnitt der beste Weg das Pivotelement zu finden aber keine Garantie auf gute Laufzeit was ja im Endeffekt aber mehr ein Quicksort-Problem ist. Aber eben auch genau der Grund weswegen Quicksort nie schön sein kann.

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).
Und im Endeffekt ist die Variante von Fluxx die weitläufig bekannteste und wohl auch beste Lösung.
Obwohl noch eine kleine Verbesserung geht:

if(i<=j){ 
        if(i<j){
            Tnode* Temp=Vec[i]; 
            Vec[i]=Vec[j]; 
            Vec[j]=Temp; 
        }

            ++i; --j; 
        }

Da wird dann eine Vertauschung gespart was ja datenabhängig viel ausmachen kann.

[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);
}

[MisterX]

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