Effizienz von Sortieralgorithmen

Name:

Effizienz und Laufzeit

In der Informatik dauern Vergleiche und der Tausch von Werten in Variablen normalerweise nur Bruchteile einer Sekunden. Doch wenn wir sehr viele dieser Vergleiche/Tausche machen müssen ist die Effizienz der Algorithmen auf einmal interessant. Entsprechend wollen wir wissen, welcher der uns bekannten Sortieralgorithmen am schnellsten ist. Dazu Vergleichen wir den sogenannten Worst-Case (längst mögliche Dauer) und Best-Case (kürzest mögliche Dauer) der verschiedenen Algorithmen. In unserem Beispiel verwenden wir einen Array mit 10 Zahlen. Fülle die Tabelle entsprechend aus.

Algorithmus

Best-Case

# Vergleiche

Worst-Case

# Vergleiche

Best-Case

Tausche

Worst-Case

Tausche

Bubble-Sort

45 = $\frac{9 \cdot 8}{2}$

Selection-Sort

Insertion-Sort

O-Notation (Das Landau Symbol)

In der Informatik verwendet man die O-Notation, um die Laufzeiten von Programmen abzuschätzen. Alle drei uns bekannten Sortieralgorithmen werden mit der Notation O( $n^{2}$ ) bezüglich der Laufzeit abgeschätzt. Dabei steht n für die Anzahl an zu sortierenden Zahlen im Array. Das bedeutet, dass wir uns fast n Mal fast alle n Zahlen im Array anschauen müssen. Wenn wir beispielsweise jedes der Elemente nur einmal anschauen könnten, wäre die Laufzeit O(n).

Schnellere Sortieralgorithmen???

Es gibt auch Sortieralgorithmen mit einer Laufzeiten von O(n log(n)) (etwas besser als O( $n^{2}$ )) oder sogar O(n). Diese haben jedoch andere Schwächen, wodurch sie in der Praxis häufig trotzdem länger brauchen. Das ist jedoch nur ein kleiner Ausblick auf die vielen anderen spannenden Algorithmen und Analysen, die wir irgendwann mal betrachten können.

Mathe-Fact: Gaußsche Summenformel

100 + 99 + 98 + ... + 1 = $\frac{100 \cdot ( 100 + 1 )}{2}$ = 5050

Oder allgemein n + n-1 + n-2 + ... + 1 = $\frac{n \cdot ( n + 1 )}{2}$