Quicksort

Quicksort ist ein instabiler Sortieralgorithmus, der mit dem Entwurfsprinzip Divide and Conquer arbeitet.

Idee

• Wähle Pivot-Element (erstes, letztes, median oder zufällig)
• Schiebe kleinere Elemente nach links und größere Elemente nach rechts
  • Eine Möglichkeit wäre mit einer for- Schleife und einem Zähler:
  • Die for-Schleife hat zwei Zähler:
  • i, welches einfach durchiteriert und pos
  • Ist das i-te Element kleiner als der Pivot, wird es mit dem pos-ten Element vertauscht und pos wird um 1 erhöht
  • Am Schluss wird das Pivot-Element mit dem pos-Element getauscht
• Wiederhole dies jeweils mit der linken und rechten Teilliste

Implementierung

quickSort(int[] array, int start, int end) {
	if (start < end) {
		int pos = divide(array, start, end);
		quickSort(array, start, pos - 1);
		quickSort(array, pos + 1, end);
	}
}
 
int divide(int[] array, int start, int end) {
	int pivot = array[start];
	
	int pos = start + 1;
	for (int i = start + 1; i <= end; i++) {
		if (array[i] <= pivot) {
			swap(array, pos, i);
			pos++;
		}
	}
	pos--;
	swap(array, start, pos);
	return pos;
}

Laufzeit

Im Best Case und Average Case asymptotisch optimal

Siehe auch

• Quicksort Analyse (PDF)