Sortierverfahren: Quicksort

Quicksort ist ein Sortierverfahren, welches wie Mergesort nach dem teile und hersche Prinzip arbeitet. Quicksort arbeitet inplace ist jedoch nicht stabil. Quicksort wurde 1961 von Tony Hoare publiziert und gewann schnell an Beliebtheit, da es weitaus schneller sortierte als Heap- oder Mergesort.

Angeberwissen: Quicksort
Tony Hoare entwickelte Quicksort als er als ein Austauschstudent in der Sowjetunion studierte. Zu seiner Aufgabe gehörte es Wörter der russischen Sprache zu sortieren. Ihm war schnell klar, dass Insertionsort nicht wirklich performant war und so entwickelte er 1959 die erste Version von Quicksort.
Als er wieder zurück in England war sollte er einen Sortieralgorithmus schreiben und wettete mit seinem Boss um einen Sixpence, dass er einen besseren Algorithmus kenne. Er gewann die Wette und publizierte 1961 seinen als Quicksort bezeichneten Algorithmus

Bei jeder Iteration von Quicksort wird zunächst ein Pivot-Element bestimmt. Dieses Element dient dazu das Feld in zwei Hälften aufzuteilen. Um ein geeignetes Pivot-Element zu finden gibt es unterschiedliche Strategien. Die verbreitetste ist es das jeweils letzte Element aus dem Feld auszuwählen.

Das Feld wird mit Hilfe des Pivot-Element in jeweils ein Feld mit kleineren Elementen und in ein Feld mit größer oder gleich großen Elementen wie das Pivot-Element aufgeteilt. Das Pivot-Element wird dann an die Stelle zwischen beiden Feldern gesetzt, wo sich seine Endposition befindet. Die Elemente innerhalb des rechten Feldes müssen dabei nicht alle verschoben werden, sondern nur das linke mit dem Pivot-Element ausgetauscht werden. Im Anschluss wird der selbe Algorithmus nun auf das linke und das rechte Teilfeld angewandt. Dies geschieht so lange, bis alle Felder in einzelne Elemente aufgeteilt wurden. Dadurch, dass dabei immer die kleinen von den großen Elementen getrennt wurden sind alle Elemente am Ende des Algorithmus geordnet.

public class Quicksort {

	public static <T extends Comparable<T>>void sort(T[] source) {
		sort(source, 0, source.length - 1);
	}
	
	public static <T extends Comparable<T>>void sort(T[] source, final int start, final int end) {
		if (start < end) {
			final int pivot = divide(source, start, end);
			sort(source, start, pivot - 1);
			sort(source, pivot + 1, end);
		}
	}
	
	public static <T extends Comparable<T>>int divide(T[] source, final int start, final int end) {
		T pivot = source[end];
		int right = end - 1;
		int left = start;
		
		do {
			while(source[left].compareTo(pivot) < 0 && left < end -1) {
				left++;
			}
			while(source[right].compareTo(pivot) >= 0 && right > start) {
				right--;
			}
			if (left < right) {
				ArrayTools.swap(source, left, right);
			}
		}
		while (left < right);
		
		if (source[left].compareTo(pivot) >= 0) {
			ArrayTools.swap(source,  left, end);
			return left;
		}
		
		return end;
	}
}

Wie bei dem Mergesort-Algorithmus kann auch Quicksort iterativ geschrieben werden. In dem folgenden Code wird eine Variante mit einer Fifo-Queue benutzt.

public class IterativeQuicksort {

	public static <T extends Comparable<T>>void sort(T[] source) {
		final Queue<QuicksortPair> queue = new FifoQueue<>();
		queue.enqueue(new QuicksortPair(0, source.length - 1));
		
		while(queue.size() > 0) {
			final QuicksortPair pair = queue.dequeue();
			if (pair.getStart() < pair.getEnd()) {
				final int pivot = Quicksort.divide(source, pair.getStart(), pair.getEnd());
				queue.enqueue(new QuicksortPair(pair.getStart(), pivot - 1));
				queue.enqueue(new QuicksortPair(pivot + 1, pair.end));
			}
		}
	}
	
	protected static class QuicksortPair {
		int start;
		int end;
		
		public QuicksortPair(int start, int end) {
			super();
			this.start = start;
			this.end = end;
		}

		public int getStart() {
			return start;
		}

		public int getEnd() {
			return end;
		}
		
	}
}

Komplexität