Schnelle Sortieralgorithmen

Abstract

Wie wichtig das Sortieren ist, wurde schon in Kap. 2 beschrieben. Eine effiziente Suche in einer Menge von Daten, wie die in Kap. 1 vorgestellte Binärsuche, ist nur möglich, wenn die Menge vorher sortiert wurde. Stellt euch z. B. die Suche im Telefonbuch von Berlin vor, wenn dieses nicht alphabetisch sortiert wäre. Bei diesem Beispiel haben wir es, wie oft in der Praxis, mit Millionen von Objekten zu tun, die zu sortieren sind. Deswegen ist es wichtig, effiziente Sortieralgorithmen zu finden, d. h. solche, die auch bei großen Datenmengen relativ kurze Laufzeiten haben, und diese können für verschiedene Algorithmen für das gleiche Problem sehr unterschiedlich ausfallen.