sortieren

Sorting (Sortieren)

Kurz: Das Anordnen der Elemente einer Datenstruktur in eine bestimmte Reihenfolge — meist aufsteigend oder absteigend nach einem Vergleichskriterium.

Genauer: Sortieralgorithmen unterscheiden sich stark in ihrer Effizienz bei großen Datenmengen — einfache Verfahren wie Bubble Sort sind leicht verständlich, aber bei vielen Elementen sehr langsam, während fortgeschrittene Verfahren (Merge Sort, Quick Sort) deutlich effizienter skalieren. Die meisten Sprachen bringen bereits stark optimierte Sortierfunktionen in ihrer Standardbibliothek mit, sodass ein eigener Sortieralgorithmus in der Praxis selten nötig ist.

Im Detail

Ein einfaches, leicht nachvollziehbares Sortierverfahren ist Bubble Sort: Es vergleicht wiederholt benachbarte Elemente und tauscht sie, wenn sie in falscher Reihenfolge stehen — nach genug Durchläufen “blubbert” das größte Element wie eine Blase nach oben:

def bubble_sort(liste):
    n = len(liste)
    for i in range(n):
        for j in range(n - i - 1):
            if liste[j] > liste[j + 1]:
                liste[j], liste[j + 1] = liste[j + 1], liste[j]
    return liste

Bubble Sort ist leicht zu verstehen und zu implementieren, aber mit O(n²) (siehe Algorithmen) bei großen Listen extrem langsam — eine Verdoppelung der Listengröße vervierfacht ungefähr die benötigte Zeit. In der Praxis wird es fast ausschließlich zu Lernzwecken eingesetzt, nicht in echtem produktivem Code.

Beim Sortieren gibt es zwei wichtige Eigenschaften, die über die reine Geschwindigkeit hinaus relevant sind:

• Stabilität: Ein stabiler Sortieralgorithmus bewahrt die relative Reihenfolge gleicher Elemente. Sortiert man z. B. eine Liste von Personen erst nach Nachname und dann (stabil) nach Vorname, bleiben Personen mit gleichem Vornamen weiterhin nach Nachname sortiert — bei einem instabilen Algorithmus wäre diese Reihenfolge nicht garantiert.
• In-Place vs. zusätzlicher Speicher: Manche Algorithmen sortieren direkt innerhalb der ursprünglichen Datenstruktur (wenig zusätzlicher Speicherbedarf), andere bauen eine komplett neue, sortierte Struktur auf (mehr Speicher, aber manchmal einfacher zu parallelisieren).

Weil die eingebauten Sortierfunktionen der Standardbibliotheken (meist Varianten von Merge Sort oder Quick Sort) über Jahre optimiert und gründlich getestet wurden, ist ein eigener, selbstgeschriebener Sortieralgorithmus in echtem Produktivcode fast nie eine gute Idee — außer man muss nach einem sehr speziellen, nicht standardmäßig unterstützten Kriterium sortieren, wofür die meisten Bibliotheken aber ohnehin eine Möglichkeit bieten, ein eigenes Vergleichskriterium (statt eines kompletten eigenen Algorithmus) anzugeben.

Siehe auch: Advanced Sorting, Algorithms, TreeSet