2. Quicksort

2.1 Historie/Hintergrund

2.2 Der Algorithmus

• Alle Elemente links vom Trennelement sollen kleiner oder gleich dem Trennelement sein.
• Alle Elemente rechts vom Trennelement sollen größer oder gleich diesem sein.
• Das Trennelement selbst soll an seine endgültige Stelle in der zu sortierenden Folge gelangen.

2.3 Zur programmiertechnischen Realisierung

void quicksort(int a[], int l, int r){		//a=Array, l=linker Rand, r=rechter Rand
    if(r>l){					//solange mehr als 1 Folgenelement existiert
        int i=l-1, j=r, tmp;			//Variableninitialisierung mit Folgenrändern
        for(;;){				//Endlosschleife; bricht ab, wenn i>=j
            while(a[++i]<a[r]);			//inkrem., bis größeres  Element gefunden wird
            while(a[--j]>a[r] && j>i);		//dekrem., bis kleineres Element gefunden wird
            if(i>=j) break;			//brich ab, wenn sich die Folgenzeiger treffen
            tmp=a[i]; a[i]=a[j]; a[j]=tmp;	//tausche kleineres mit größerem Element
        }
        tmp=a[i]; a[i]=a[r]; a[r]=tmp;		//tausche Trennelement

        quicksort(a, l, i-1);			//rekursiver Aufruf für linke Teilfolge
        quicksort(a, i+1, r);			//rekursiver Aufruf für rechte Teilfolge
    }
}

2.4 Ein Beispiel

1.1) Linker und rechter Folgenzeiger wurden initialisiert, 6 als Trennelement festgelegt. Von links wurde mit 6 ein Element gefunden, welches größer gleich dem Trennelement ist, von rechts wurde mit 5 ein kleineres Element gefunden. Diese werden miteinander vertauscht.
1.2) Von links wird mit 13 sofort ein Element gefunden, welches größer als das Trennelement 6 ist. Von rechts läuft der Folgenzeiger bis 1, welches kleiner ist. Diese Element werden wieder getauscht.
1.3) 7 wird als größeres, 2 als kleineres Element gefunden und miteinander vertauscht.
1.4) Von links wird 9 als größeres, von rechts 2 als kleineres Element gefunden. Allerdings werden diese nicht miteinander vertauscht, da sich die beiden Folgenzeiger überschneiden und die Endlosschleife terminiert.
1.5) Zum Schluss dieser ersten Vorsortierung wird noch das Trennelement mit dem äußerst linken Element der rechten Teilfolge getauscht und erhält damit seinen endgültigen Platz. Anschließend erfolgen die rekursiven Aufrufe für linke und rechte Teilfolge. Wie gut zu sehen ist, wurde die Folge in 2 Teile "geteilt": die Elemente in der linken Teilfolge sind kleiner und die in der rechten Teilfolge größer als das verbindende Trennelement.
2.1) Der erste rekursive Aufruf erfolgt für die linke Teildatei. 2 als letztes Element ist Trennelement. Von links wird 5 als größer und von rechts 1 als kleiner gefunden und miteinander vertauscht.
2.2) Da sich beide Zeiger überschneiden, wird nichts getauscht und die Endlosschleife terminiert.
2.3) Zum Schluss wird das Trennelement wieder an seine endgültige Position an den linken Rand der rechten Teilfolge getauscht. Der rekursive Aufruf für die linke Teilfolge kehrt sofort zurück, da diese nur aus einem Element besteht, also folgt der Aufruf für die rechte Teilfolge.
3.) 5 ist Trennelement. Die beiden Zeiger überschneiden sich sofort nach dem ersten Auffinden von größer-/kleiner-gleich-Elementen, sodass keine Vertauschungen stattfinden und die Endlosschleife zurückkehrt. Dann erfolgt das Tauschen des Trennelementes an die linke Position der rechten Teilfolge, welche allerdings schon die momentane Position des Trennelementes ist - daher kommt es zu keiner Änderung in der Folgenordnung. Die linke Teilfolge enthält 1 Element, die rechte Teilfolge sogar keines - infolge dessen kehrt die Funktion zurück.
4.1) Die linke Teildatei der Ausgangsfolge gilt nun als sortiert, da alle Aufrufe bis zur ersten Rekursionsebene zurückkehren. Nun folgt der Aufruf für die rechte Teildatei. Zunächst ist 9 Trennelement, der linke Zeiger führt zur 13 als größeres und der rechte Zeiger zu 6 als kleineres Element, welche folglich miteinander vertauscht werden.
4.2) Beim nächsten Halt der beiden Zeiger überschneiden sich diese schon, sodass die Endlosschleife abbricht.
4.3) Nach dem Tausch des Trennelementes an seine endgültige Position erfolgt der Aufruf für die linke Teilfolge.
5.1) 6 ist Trennelement, die Endlosschleife terminiert bereits beim ersten Anhalten der Zeiger, da der rechte Zeiger auf einem kleineren Index steht als der linke Zeiger.
5.2) Das Trennelement wird auf seine Endposition getauscht. Die linke Teildatei ist leer, daher erfolgt der Aufruf für die rechte Teilfolge.
6.1) 7 ist Pivot, nach dem Lauf der beiden Zeiger stehen diese auf demselben Element, sodass die Endlosschleife abbricht.
6.2) Das Trennelement kommt auf seine endgültige Position und die Funktion kehrt zurück.
7.1) In dieser äußerst rechten Teilfolge ist 15 das Pivot. Die beiden Zeiger überschneiden sich wieder sofort nach dem ersten Durchlauf, sodass nichts getauscht wird, nur das Trennelement noch an seine korrekte Position gelangt, auf welcher es sich jedoch schon befindet, sodass keine Reihenfolgeänderungen stattfinden.
7.2) Zu guter letzt erfolgt der Aufruf für diese linke Teilfolge. 13 ist Trennelement, der erste Halt der Zeiger führt gleich zu einem Abbruch der Endlosschleife, sodass nichts getauscht wird und das Trennelement hat schon seine Endposition inne.
8.) Alle Aufrufe kehren zurück bis zur ersten Rekursionsebene. Dort wurden linke und rechte Teildatei behandelt, sodass auch dieser Aufruf beendet ist - die Folge gilt als sortiert!

2.5 Verbesserungen

  int m=(l+r)/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; }

  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)/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] && j>i);
		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);
	}
  }

  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] && j>i);
		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;
	  }
	}
  }

  //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] && j>i);
		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;
	}
  }

  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)/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] && j>i);
		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;
	  }
	}
  }

2.6 Laufzeitbetrachtungen

(c) 2004 by RTC, www.linux-related.de
Dieses Dokument unterliegt der GNU Free Documentation License