Sortierverfahren vergleichen

1

Worauf es beim Vergleich ankommt

Selectionsort, Insertionsort und Bubblesort liefern dasselbe Ergebnis. Unterschiedlich ist, wie viel sie dafür tun — gemessen wird das rechnerunabhängig durch Zählen.

Vergleiche:wie oft zwei Elemente verglichen werden — das wichtigste Maß für die Laufzeit.
Umstellungen:Vertauschungen (Selection-, Bubblesort) bzw. Verschiebungen (Insertionsort). Ein Tausch schreibt zwei Plätze der Reihung, eine Verschiebung nur einen.
Speicher:alle drei sortieren in-place: außer der Reihung nur eine Hilfsvariable (hilf bzw. aktuell) und Zählvariablen.
Stabilität:gleiche Werte behalten ihre Reihenfolge. Selectionsort ist nicht stabil: aus 5a 5b 2 wird durch den Tausch 2 5b 5a.
Vorsortiert:nutzt das Verfahren aus, dass die Daten schon fast in Ordnung sind?

Vergleich der drei Sortierverfahren für n Elemente
	Selectionsort	Insertionsort	Bubblesort mit Abbruch
Vergleiche	immer \(\frac{n(n-1)}{2}\)	\(n-1\) bis \(\frac{n(n-1)}{2}\)	\(n-1\) bis \(\frac{n(n-1)}{2}\)
Umstellungen	höchstens \(n-1\)	0 bis \(\frac{n(n-1)}{2}\)	0 bis \(\frac{n(n-1)}{2}\)
stabil	nein	ja	ja
vorsortiert	keine Ersparnis	\(n-1\) Vergleiche	\(n-1\) Vergleiche

Bester Fall:bereits sortierte Eingabe — ein Durchlauf ohne Umstellung genügt (außer bei Selectionsort).
Ungünstigster Fall:umgekehrt sortierte Eingabe — jedes Paar steht falsch herum.

2

Messen und entscheiden

Wähle Verfahren, Eingabe und Länge n und starte die Messung mit ▶. Trage jedes Ergebnis in die Messtabelle ein. Miss dann für ein Verfahren n = 10, 20, 40, 80 und vergleiche die Spalte „Faktor“.

Verfahren

Eingabe

Länge

Messtabelle
Verfahren	Eingabe	n	Vergleiche	Umstell.	Faktor

Halte fest: Verdoppelt man n, steigt die Zahl der Vergleiche im ungünstigsten Fall bei allen drei Verfahren etwa auf das Vierfache. Nur bei vorsortierter Eingabe wachsen Insertionsort und Bubblesort mit Abbruch bloß linear.

Herleitung:

\(V(n)=\dfrac{n(n-1)}{2}=\dfrac{n^2}{2}-\dfrac{n}{2}\)

ausmultiplizieren

Für große n fällt \(\frac{n}{2}\) kaum ins Gewicht: \(V(n)\sim\frac{n^2}{2}\) — quadratisches Wachstum.

\(V(2n)\approx\dfrac{(2n)^2}{2}=4\cdot\dfrac{n^2}{2}\)

n → 2n

Das Quadrat macht aus dem Faktor 2 bei n den Faktor 4 bei der Arbeit.

\(V(2n)\approx4\cdot V(n)\)

Ergebnis

Beispiel: \(V(1000)=499\,500\), \(V(2000)=1\,999\,000\) — Faktor 4,002.

Fast sortiert:Insertionsort (oder Bubblesort mit Abbruch) — nahe an \(n-1\) Vergleichen.
Schreiben teuer:Selectionsort — höchstens \(n-1\) Vertauschungen, z. B. bei großen Datensätzen oder Flash-Speicher.
Stabil nötig:Insertionsort oder Bubblesort, z. B. erst nach Namen, dann nach Klasse sortieren.
Zufällige Daten:meist Insertionsort — im Mittel etwa \(\frac{n^2}{4}\) Vergleiche, halb so viele wie Selectionsort.

Merke

Alle drei Verfahren: in-place, ungünstigster Fall \(\sim\dfrac{n^2}{2}\) Vergleiche — doppelte Länge, etwa vierfache Arbeit.

3

Allgemeine Hinweise

Gleich viele Umstellungen, ungleich teuer

Insertionsort und Bubblesort stellen dieselbe Anzahl falsch geordneter Paare richtig. Ein Tausch braucht aber drei Zuweisungen, eine Verschiebung nur eine.

Zählen statt Stoppen

Eine Zählvariable direkt vor dem Vergleich liefert auf jedem Rechner dieselbe Zahl. Eine Zeitmessung schwankt mit Rechner, Auslastung und Programmiersprache.

Quadratisch wird schnell zu langsam

Eine Million Werte brauchen im ungünstigsten Fall rund \(5\cdot10^{11}\) Vergleiche — bei einer Milliarde Vergleichen pro Sekunde über 8 Minuten.