Komplexität von Sortieralgorithmen

Untersuchung der Laufzeit von Insertion-, Bubble- und Quicks

Author: Jakob Hartmann
Length: 20 page(s)
Language: Deutsch
Written: 2010
Sales Rank: -
Views: 437

In dieser Arbeit stellen wir fest, dass das Sortieren von Daten im heutigen Computerzeitalter von zentraler Bedeutung ist und es verschiedene Algorithmen für dieses Problem gibt. Diese Algorithmen haben verschiedene Eigenschaften, unter anderem die Laufzeit, mit der wir uns näher beschäftigen. Die Laufzeit lässt sich meist nicht exakt berechnen, sondern nur ihre Größenordnung. Sie ist bei den meisten Sortierverfahren von der Art der Eingabedaten abhängig, es gibt für sie einen besten, einen schlechtesten und einen durchschnittlichen Fall (Best-, Worst- und Average-Case).

Wir untersuchen zunächst die Laufzeit zweier einfacher Sortieralgorithmen, Insertionsort und Bubblesort. Beide Verfahren haben im Average- und Worst-Case eine quadratisch ansteigende Laufzeit, Insertionsort hat im Best-Case, bei bereits sortierten Feldern, jedoch nur eine lineare Komplexität. Des Weiteren untersuchen wir Quicksort, ein höheres Sortierverfahren. Es ist zwar im Worst-Case wieder quadratisch, im Average-Case steigt die Laufzeit aber nur loglinear (n∙ log n).

Abschließend können wir festhalten, dass es keinen besten Sortieralgorithmus gibt, sondern je nach Problemstellung ein anderes Verfahren am effizientesten sein kann. Wir müssen also zuerst unser Problem analysieren, bevor wir einen passenden Algorithmus auswählen können.

Diese Facharbeit wurde mit 13 von 15 Punkten (sehr gut) bewertet.

No review yet.