Quicksort - wie man den Algorithmus noch schneller machen kann!

Quicksort an sich ist ja bereits ein sehr effizienter und alltagsbewährter Algorithmus. Zu seinen Vorzügen zählen die extrem kurze innere Schleife, die große Anpassungsfähigkeit an praxisnahe Projekte sowie die gute Laufzeit mit durchschnittlichen N log N Operationen. Dies sind auch die wesentlichen Gründe, warum sich dieser bereits 1960 von C.A.R. Hoare entwickelte Algorithmus solange halten konnte. Auch wenn viele andere Algorithmen der Leistungsfähigkeit von Quicksort nahe kommen oder sie im durchschnittlichen bzw. ungünstigsten Fall gar übertreffen mögen, so ist Quicksort im Alltag meist doch besser verwendbar...
Die Versuchung ist demnach groß, diesen Algorithmus noch weiter verbessern zu wollen, als wie er ursprünglich implementiert wurde, sind immer schnellere Sortieralgorithmen zudem doch eine der größten Herausforderungen der Informatik. Und tatsächlich wurden bereits viele Vorschläge zur Verbesserung und Optimierung eingebracht, die meisten führten allerdings zu einer herben Enttäuschung, da Modifikationen an einem Teil des Algorithmus in einer schlechteren Laufzeit in anderen Teilen resultierten. Dennoch haben sich drei wesentliche Modifikationen bewährt gemacht, die auch zu einer spürbaren Effizienzsteigerung führen können. Da ich auf linux-related.de die Sortieralgorithmen im Allgemeinen nicht vorstellen wollte und da es etliche Seiten zu diesem Thema gibt, lasse ich eine ausführliche Quicksort-Beschreibung sowie die erste Modifikation, nämlich die Beseitigung der Rekursion, außen vor.
Ziel dieses Textes ist es hingegen, erst kurz auf den klassischen Quicksort-Algorithmus einzugehen und dann die beiden anderen Verbesserungen, nämlich das Finden eines besseren Trennelements (median-of-three) und eine elegantere Lösung für das Abarbeiten von kleinen Teilfeldern mittels insertion sort ausführlicher zu behandeln.

1. Klassisches Quicksort

Hier zur Vollständigkeit der C-Code, welcher den klassischen Quicksort-Algorithmus zeigt:

  void quicksort(int a[], int l, int r){
	if(r>l){
	  int i=l-1, j=r, tmp;
	  for(;;){
		while(a[++i]<a[r]);
		while(a[--j]>a[r]);
		if(i>=j) break;
		tmp=a[i]; a[i]=a[j]; a[j]=tmp;
	  }
	  tmp=a[i]; a[i]=a[r]; a[r]=tmp;

	  quicksort(a, l, i-1);
	  quicksort(a, i+1, r);
	}
  }

Kurz ein paar Bemerkungen, wie dieser Algorithmus arbeitet: bei jedem Durchlauf der Funktion quicksort() wird das Feld a[] in zwei Teilfelder zerlegt. Das erste Teilfeld erstreckt sich von l bis zu einem zerlegenden Element, das zweite von diesem zerlegenden Element bis zu r. Ziel dieser Funktion ist es, zunächst r als zerlegendes Element auszuwählen. Nun muss a[] so umsortiert werden, dass alle Elemente, die kleiner als a[r] sind, in das linke Teilfeld und alle Elemente, die größer a[r] sind, in das rechte Teilfeld verschoben werden. Im linken Teilfeld befinden sich jetzt also ausschließlich Elemente, die kleiner als a[r] sind und im rechten Teilfeld Elemente, die größer a[r] sind
Mittels rekursiver Funktionsaufrufe für beide Teilfelder findet diese Verschiebung nun solange statt, wie r>l ist. Sollte ein Teilfeld also nur noch aus einem Element bestehen, so kehrt die Funktion ohne weitere rekursive Aufrufe zurück. Durch die Rekursion und die Aussage "Elemente im linken Teilfeld sind kleiner und Elemente im rechten Teilfeld größer als a[r]" liegt nach Beendigung der Rekursion ein sortiertes Feld vor.
Im Code geschieht die Aufteilung in Teilfelder folgendermaßen: als zerlegendes Element wird zunächst das am weitesten rechte benutzt, eine Vorgehensweise, die für zufällige Permutationen durchaus Sinn macht, im ungünstigsten Fall aber keine gute Wahl ist, wie wir später noch sehen werden. Ein Zähler i arbeitet sich nun von der linken Feldgrenze nach oben, ein Zähler j von der rechten Feldgrenze nach unten. Dabei wird i solange inkrementiert, bis ein Element auftritt, welches größer als a[r] ist. j hingegen wird solange dekrementiert, bis ein Element auftritt, welches kleiner als a[r] ist. Wenn i nicht über j hinaus gezählt wurde, so werden a[i] und a[j] vertauscht, da a[i] ein kleineres und a[j] ein größeres Element als a[r] ist. Diese Prozedur wird solange wiederholt, bis i>=j ist, dann wird die Endlosschleife beendet.
Nachfolgend kommt es nochmals zu einem Austausch: das zerlegende Element wird mit a[i] vertauscht. Warum? Ganz einfach: wenn die Zähler i und j gestoppt haben, dann befindet sich i an der Stelle, wo alle Elemente links kleiner und alls Elemente rechts von i (inkl. i) größer als a[r] sind. a[r] wird also in seine endgültige Position im sortierten Feld a[] verschoben und nachfolgend nicht mehr betrachtet. Nun folgen die rekursiven Funktionsaufrufe. Der erste für das linke Teilfeld von l bis i-1, der zweite für das rechte Teilfeld von i+1 bis r (wie eben erwähnt: a[i] wird nun nicht weiter betrachtet). So setzt sich die Prozedur fort, bis am Ende alle rekursiven Aufrufe zurückkehren.

Wie gesagt: dies sollte nur noch einmal eine kleine Behandlung des Quicksort-Algorithmus sein, welche eher zur Wiederholung und zur Vertiefung als wie zur Einführung gedacht ist. Für eine ausführlichere Darstellung des klassischen Algorithmus bitte ich spezielle Literatur oder Webseiten zu Rate zu ziehen, dies soll nicht Anspruch des vorliegenden Textes sein...

2. Besseres Trennelement finden (Median-of-three)

Als Einleitung zu dieser Quicksort-Verbesserung zunächst einmal die Betrachtung des günstigsten Falls: dieser tritt beim Quicksort-Algorithmus dann ein, wenn das betrachtete Teilfeld bei jedem Aufruf von quicksort() in zwei gleich große Stücke zerteilt wird. Äquivalent dazu der ungünstigste Fall, den man beobachten kann, wenn eines der beiden Stücke nur ein Element enthält. In diesem ungünstigsten Fall ruft sich quicksort() N mal selber auf (N=Anzahl der Feldelemente), zudem benötigt der Algorithmus N²/2 Vergleiche, ist also genauso langsam wie Bubble Sort, welches man ja nicht wirklich als effizient bezeichnen kann ;o)
Der ungünstigste Fall kann demnach z.B. dann eintreten, wenn man a[r] als zerlegendes Element nimmt und den Quicksort auf ein bereits sortiertes Feld loslässt. Eine sehr einfache Möglichkeit in diesem Fall wäre es, das Element a[l+(r-l)/2] als Trennelement zu benutzen, welches ja das (vom Index her) mittlere Feldelement darstellt. Hierbei kann es allerdings genauso leicht passieren, dass man ein Element erwischt, welches an einem der beiden Enden der Werteskala der Feldelemente angesiedelt ist.
Eine sehr einfache und augenscheinlich sinnvolle Lösung ist hingegen, drei Elemente aus dem Feld zu entnehmen und das (wertmäßig) mittlere von ihnen als Trennelement zu betrachten. Zufallsgeneratoren sind in diesem Fall übertrieben, eine einfache Lösung des Herausnehmens der drei Elemente besteht darin, das erste Element mit a[l], das zweite mit a[l+(r-l)/2] und das dritte Element mit a[r] fest zu legen. Das Herausfinden und der Austausch zwischen den Elementen findet wie im folgenden C-Code gezeigt statt:

  int m=l+(r-l)/2;
  if(a[l]>a[m])
    { tmp=a[l]; a[l]=a[m]; a[m]=tmp; }
  if(a[l]>a[r])
    { tmp=a[l]; a[l]=a[r]; a[r]=tmp; }
  else if(a[r]>a[m])
    { tmp=a[r]; a[r]=a[m]; a[m]=tmp; }

Es ist zu erkennen, dass sich das wertmäßig mittlere Element der drei nach der Anwendung dieses Algorithmus an der Stelle a[r] befindet. Dies hat Vorteile, da somit dieses Element vom Zähler j des Quicksort-Algorithmus nicht betrachtet werden muss und es sogleich an seine Stelle im sortierten Feld eingeordnet wird. Das spart natürlich Rechenzeit.
Die alles entscheidende Frage: Was bringt uns das? Die Beantwortung ist nicht leicht und es kann keine allgemeine Leistungskenngröße geben, was ganz einfach zu erklären ist: auch beim Herausnehmen und Vergleichen von drei Elementen kann es dazu kommen, dass man eben die drei größten bzw. kleinsten Elemente entnimmt, speziell kann ohne Verwendung eines Zufallsgenerators natürlich auch ein Feld konstruiert werden, welches sich am ungünstigsten für diesen Fall verhält. In der Praxis, und hier gehen wir vom Durchschnitt der Fälle aus, wird die Chance, eines der mittleren Elemente zu treffen, jedoch deutlich erhöht und somit erhöht sich natürlich auch die Wahrscheinlichkeit, dass ein Feld in zwei etwa gleich große Teilfelder zerlegt wird. Im Allgemeinen kann man von einer Geschwindigkeitssteigerung von 5% und (eher) mehr ausgehen.
Hier noch einmal der komplette verbesserte Quicksort-Algorithmus mit der Methode "median of three":

  void qsort_median(int a[], int l, int r){
	if(r>l){
	  int i=l-1, j=r, tmp;
	  if(r-l > 3){ //Median of three
		int m=l+(r-l)/2;
		if(a[l]>a[m])
		  { tmp=a[l]; a[l]=a[m]; a[m]=tmp; }
  		if(a[l]>a[r])
		  { tmp=a[l]; a[l]=a[r]; a[r]=tmp; }
  		else if(a[r]>a[m])
		  { tmp=a[r]; a[r]=a[m]; a[m]=tmp; }
	  }

	  for(;;){
		while(a[++i]<a[r]);
		while(a[--j]>a[r]);
		if(i>=j) break;
		tmp=a[i]; a[i]=a[j]; a[j]=tmp;
	  }
	  tmp=a[i]; a[i]=a[r]; a[r]=tmp;

	  qsort_median(a, l, i-1);
	  qsort_median(a, i+1, r);
	}
  }

Zum Abschluss dieses Verbesserungsvorschlags ein weiterer Ausblick: man könnte nun natürlich auf die Idee kommen, mehr Elemente als drei zu betrachten oder gar alle Elemente, um die Chance weiter zu erhöhen, das mittlere Element zu ermitteln. Es sollte hierbei allerdings angedacht werden, dass es unter Umständen auch zu Geschwindigkeitsverlusten kommen kann, wenn man viele Elemente betrachtet und miteinander vertauscht. Tatsächlich gibt es einen Algorithmus, welcher in linearer Zeit das mittlere von N Elementen herausfinden kann, da dieser allerdings erstens trotzdem noch allzuviel Zeit in Anspruch nimmt, zweitens ebenfalls auf Teilen des Quicksort-Algorithmus basiert und drittens an dieser Stelle den Rahmen zu weit ziehen würde, lassen wir ihn außen vor. In der Praxis würde ich dieses Verfahren zudem als nicht sehr praktikabel bezeichnen...

3. Behandlung kleiner Teilfelder

Neben der Überlegung, wie kleine Teilfelder zu vermeiden sind (median-of-three), kann man sich auch über die Behandlung solcher Gedanken machen. Wenn man sich den klassischen Quicksort anschaut, so stellt man fest, dass die Zerlegung (die rekursiven Funktionsaufrufe) für viele kleine Teilfelder bishin zur Feldgröße 1 stattfindet. Folglich kann man festlegen, dass eine Möglichkeit gefunden werden muss, Quicksort für kleine Teilfelder schneller ablaufen zu lassen. Eine Möglichkeit, die oft angewandt wird, besteht darin, insertion sort auf ein Teilfeld loszulassen, falls die Größe des Feldes unter einen konstanten Schwellwert M sinkt. Dieser Quick-/Insertion-Sort-Mix lässt sich in C-Notation wie folgt darstellen:

  void qsort_ins(int a[], int l, int r){
	int i, j, tmp;
	if(r-l > M){ //Quicksort
	  i=l-1; j=r;
	  for(;;){
		while(a[++i]<a[r]);
		while(a[--j]>a[r]);
		if(i>=j) break;
		tmp=a[i]; a[i]=a[j]; a[j]=tmp;
	  }
	  tmp=a[i]; a[i]=a[r]; a[r]=tmp;

	  qsort_ins(a, l, i-1);
	  qsort_ins(a, i+1, r);
	}
	else{ //insertion sort
	  for(i=l+1; i<=r; ++i){
	  	tmp=a[i];
	  	for(j=i-1; j>=l && tmp<a[j]; --j)
		  a[j+1]=a[j];
		a[j+1]=tmp;
	  }
	}
  }

Ist die Bedingung if(r-l > M) nicht mehr erfüllt (ist das Teilfeld also "zu klein" für Quicksort), so wird für das behandelte Teilfeld insertion sort aufgerufen, ansonsten findet weiterhin das klassische Quicksort Anwendung.
Was bringt's?: Mit dieser Methode lassen sich viele rekursive Aufrufe ersparen. In Abhängigkeit von M kann man Laufzeitverbesserungen von 20% und mehr beobachten, was wahrlich nicht zu unterschätzen ist.

Eine zweite Vorgehensweise in dieser Hinsicht beruht auf der Tatsache, dass insertion sort für sortierte Felder linear abläuft und für fast sortierte Felder effizient arbeitet. Also kann man festlegen, dass zunächst Quicksort aufgerufen wird, aber nicht mit der Abfrage if(r>l), sondern mit dem Vergleich if(r-l > M). Somit werden kleine Teilfelder von Quicksort gänzlich ignoriert. Zu seinem sortierten Feld kommt man schlussendlich, indem man dieses vorsortierte Feld einmal komplett von insertion sort durchlaufen lässt, welches in diesem Fall effektiv arbeitet. Trotzdem ist diese Vorgehensweise etwas uneffektiver als die zuerst vorgestellte, weshalb man obigen Code der folgenden C-Notation doch vorziehen sollte:

  //Hilfsfunktion für qsort_ins2()
  void qsort_M(int a[], int l, int r){
	int i, j, tmp;
	if(r-l > M){ //Quicksort
	  i=l-1; j=r;
	  for(;;){
		while(a[++i]<a[r]);
		while(a[--j]>a[r]);
		if(i>=j) break;
		tmp=a[i]; a[i]=a[j]; a[j]=tmp;
	  }
	  tmp=a[i]; a[i]=a[r]; a[r]=tmp;

	  qsort_M(a, l, i-1);
	  qsort_M(a, i+1, r);
	}
  }

  //2. Variante von Quick-/insertion-sort
  void qsort_ins2(int a[], int l, int r){
	int i, j, tmp;
	qsort_M(a, l, r); //qsort_M zur Vorsortierung
	for(i=l+1; i<=r; ++i){ //insertion sort
	  tmp=a[i];
	  for(j=i-1; j>=l && tmp<a[j]; --j)
		a[j+1]=a[j];
	  a[j+1]=tmp;
	}
  }

Bleibt noch die Frage offen, wie groß man den Schwellwert M festlegen sollte. Dies ist schwer zu beantworten und trotz vielen Suchens habe ich noch keine Funktion entdecken können, die M optimal auswählen kann. Augenscheinlich ist M abhängig von der Anzahl der Elemente N, da die Rekursionstiefe von Quicksort mit zunehmender Elementeanzahl natürlich ansteigt. Für N=10 Millionen konnte ich durch empirische Laufzeitmessung einen optimalen Wert von ungefähr M=300 ermitteln, für weniger Elemente muss M kleiner, für mehr Elemente größer gewählt werden. Ich werde mich in der kommenden Zeit noch einmal intensiver mit dem Auffinden einer optimalen Funktion zum Ermitteln von M in Abhänigkeit von N beschäftigen, welches sich vor allem auf Laufzeitmessungen stützen wird. Man darf trotzdem gespannt sein, schließlich lässt sich hiermit erheblich viel Rechenzeit sparen...

4. Beides zusammen?

Natürlich könnte man nun auf die Idee kommen, die beiden Verfahren zu kombinieren und somit eine noch größere Effizienzsteigerung zu erreichen. Dieses Vorgehen ist im folgenden C-Code fest gehalten:

  void qsort_comb(int a[], int l, int r){
	int i, j, tmp;
	if(r-l > M){ //Quicksort
	  i=l-1; j=r;
	  if(r-l > 3){ //Median of three
		int m=l+(r-l)/2;
		if(a[l]>a[m])
		  { tmp=a[l]; a[l]=a[m]; a[m]=tmp; }
		if(a[l]>a[r])
		  { tmp=a[l]; a[l]=a[r]; a[r]=tmp; }
		else if(a[r]>a[m])
		  { tmp=a[r]; a[r]=a[m]; a[m]=tmp; }
	  }

	  for(;;){
		while(a[++i]<a[r]);
		while(a[--j]>a[r]);
		if(i>=j) break;
		tmp=a[i]; a[i]=a[j]; a[j]=tmp;
	  }
	  tmp=a[i]; a[i]=a[r]; a[r]=tmp;

	  qsort_comb(a, l, i-1);
	  qsort_comb(a, i+1, r);
	}
	else{ //insertion sort
	  for(i=l+1; i<=r; ++i){
		tmp=a[i];
		for(j=i-1; j>=l && tmp<a[j]; --j)
		  a[j+1]=a[j];
		a[j+1]=tmp;
	  }
	}
  }

Doch Vorsicht: dieser Algorithmus kann uneffektiver sein als der zuvor vorgestellte insertion-/Quicksort-Mix! Grund: wählt man z.B. bei vielen Elementen N einen entsprechend angepassten großen Schwellwert M, für welchen Quicksort in insertion sort übergeht, so ist die Chance gering, in einer Teildatei, welche ja mindestens die Größe M haben muss, als Trennelement eines heraus zu greifen, welches sich im oberen bzw. unteren Teil des Feldes befindet. Somit kann es unangebracht sein, ein median-of-three (also das wertmäßig mittlere von drei Elementen) zu ermitteln, da die Vergleiche und Austauschoperationen hierbei mehr Rechenzeit kosten können als wie sie ersparen. Es ist also eher eine Gewissensfrage, ob man median-of-three und das insertion-sort-Verfahren für kleine Teilfelder kombiniert. Im Allgemeinen wird dadurch Rechenzeit erspart, trotzdem kann selbst bei zufälligen Permutationen allein die Verbesserung mittels insertion sort schneller sein. Zu kombinieren empfehle ich beide Verfahren bei klein gewählten M (also bei Feldern mit eher wenig Elementen N), doch auch dies ist subjektiv zu entscheiden und kann nicht verallgemeinert werden.

5. Outroduction

Ich hoffe mit meinem Text zwei der wichtigsten Verbesserungen für Quicksort anschaulich und verständlich illustrieren zu können. Wie anfangs schon erwähnt, so sollte hier nicht der Quicksort-Algorithmus an sich beschrieben werden, entsprechend kompakt ist auch die Erklärung zu diesem klassischen Algorithmus ausgefallen. Ich bitte dabei zu spezieller Literatur zu greifen, auch Webseiten hierfür gibt es wie Sand am Meer.
Der Text soll gezeigt haben, dass man selbst den recht schnellen Quicksort-Algorithmus noch um einiges schneller machen kann und dass es analog dazu sicher kaum einen Algorithmus gibt, den man nicht verbessern und optimieren kann. Trotzdem muss man vorsichtig sein: einige Verbesserungen können Konsequenzen haben, welche einen Algorithmus instabil oder in anderen Teilen langsamer machen können. Aufgrund dessen habe ich mich hier auch nur auf diese zwei sehr populären Verbesserungen beschränkt, die beim Sortieren großer Datenbestände noch einmal eine deutliche Geschwindigkeitssteigerung versprechen und von denen mir keine Nebenwirkungen in der Implementierung bekannt sind.
Das war's? Fast! Wie oben erwähnt versuche ich noch mit einem speziell dafür programmierten Tool eine Funktion zu ermitteln, welche in Abhängigkeit von N ein optimales M ermitteln kann. Man darf gespannt sein, wie diese Recherche ausgeht, bei positivem Ergebnis wird hier dazu auf jeden Fall demnächst ein seperater Text zu finden sein.
Lob, Kritik, Anregungen usw. immer wieder gern an mich ;o)