Sortieralgorithmen im Überblick

Wie schön, wenn man alle Daten in einer gut sortierten Liste hat und so schnell findet was man sucht. Was machen wir, wenn das mal nicht der Fall ist? Wir sortieren sie! Bei den riesigen Listen, mit denen man es in der Informatik meist zu tun hat, gestaltet sich das gar nicht so einfach. Zum Glück gibt es Sortieralgorithmen. Gucken wir uns diese hier mal genauer an, denn auch sie unterscheiden sich erheblich voneinander.

Eigenschaften von Sortieralgorithmen

Es gibt verschiedene Kriterien, nach denen man Sortieralgorithmen bewerten kann und die Wahl des richtigen Algorithmus ist abhängig von dem Anwendungsfall.

Prinzipiell unterscheidet man zwischen:

  • Zeit- oder Platzkomplexität
    • Zeitkomplexität: Menge der notwendigen Operationen
    • Platzkomplexität: Die Menge an zusätzlich benötigten Speicherplatz
  • stabil oder instabil
    • stabil: die Reihenfolge der Elemente bleibt erhalten
    • instabil: die Reihenfolge im Array wird geändert
  • in-place oder out-of-place
    • in-place: die Elemente werden direkt in der Liste getauscht;
    • out-of-place: die Elemente werden in eine neue Datenstruktur übertragen

Solltest du dich für das Thema Zeitkomplexität von Algorithmen genauer interessieren, wirf hier noch mal einen Blick rein: Algorithmen – Eigenschaften und Laufzeit. Hier gehe ich noch einmal genauer auf das Thema Zeitkomplexität ein.

Gucken wir uns nun mal einige der vergleichsbasierten Algorithmen genauer an.

Bekannteste Sortieralgorithmen

Bubblesort

Bubblesort ist der einfachste und älteste Sortieralgorithmus den du finden kannst. Hier gehst du einfach alle Elemente eines Arrays durch und vergleichst sie miteinander. Wollen wir vom kleinsten zum größten Wert sortieren und ist ein Element größer als sein Nachfolger, werden diese Elemente getauscht. Damit ist Bubblesort ein stabiler, in-place Algorithmus.

Insertionsort

Insertionsort ist im Vergleich mit anderen Algorithmen ebenfalls einfach. Der Algorithmus ist stabil und arbeitet in-place. Hier wird die Liste in zwei Bereiche unterteilt, den sortierten und den unsortierten Bereich. Die linke Seite ist immer die sortierte Seite und die Rechte die zu Sortierende. Deshalb bildet das erste Element in der Liste den sortierten Bereich. Im Anschluss geht man dann den unsortierten Bereich Element für Element durch und ordnet die Elemente an die richtige Stelle, in der sortierten Liste.

Wie das genau funktioniert gucken wir uns noch einmal in einem separaten Beitrag an.

Quicksort

Quicksort ist das am häufigsten verwendete Verfahren. Es handelt sich dabei um einen instabilen, in-place Algorithmus, dessen Implementierung stark von der Wahl der Programmiersprache und den Programmierer abhängig ist. Grundlegend lässt sich sagen, dass man immer ein Element aus der Liste bestimmt, das sogenannte Pivotelement und dieses Element bildet dann den Maßstab für Vergleiche. Im Anschluss setzen wir alle anderen Elemente an ihre richtige Position. Die neuen Positionen bestimmst du immer auf Basis des Pivotelements. Wenn keine weiteren Elemente mehr zu sortieren sind, endet der Algorithmus.

Guck dir hier am besten direkt an wie Quicksort genau funktioniert und wie du es in Java umsetzen kannst.

Mergesort

Hier handelt es sich um einen der komplexeren Algorithmen. Mergesort gehört zur Klasse der „divide and conquer“ Algorithmen. Um die Liste zu sortieren wird sie so oft halbiert bis nur noch einzelne Elemente übrig sind. Im Anschluss wird dann die Lise ‚gemerged‘. Das bedeutet, dass die vielen einzelnen ‚Listen‘, die wir hier nun haben, wieder zusammengesetzt und ihre Elemente an ihre korrekte Position gesetzt werden.

Mergesort arbeitet stabil, aber wie du dir wahrscheinlich auch schon denken konntest, gehört Mergesort zu den out-of-place und damit zu den speicherintensiven Algorithmen. Dafür ist es ein sehr schneller Algorithmus, der auch problemlos mit großen, unsortierten Listen klarkommt.

Auch Mergesort nehme ich mit dir in einem separaten Beitrag noch einmal genauer unter die Lupe.

Selection Sort

Selectionsort ist ziemlich simpel aufgebaut. Du hast eine Liste und diese Liste möchtest du sortieren, dafür suchst du einfach immer wieder nach dem Element was deine Bedingung erfüllt. Möchtest du also deine Liste vom kleinsten bis zum größten Wert sortieren, suchst du aus der Liste immer das kleinste Element raus und setzt es an seine Position. Da das ziemlich ineffektiv ist, wird hier oft von beiden Seiten parallel gearbeitet. Man spricht dann von OSSA (Optimized Selection Sort Algorithm). Dadurch das wir die Elemente direkt in der Liste tauschen, haben wir einen in-place Algorithmus, der die Reihenfolge der Elemente nicht erhält und damit instabil arbeitet.

Solltest du Fragen oder Anmerkungen haben lass doch ein Kommentar dar. Der Beitrag darf natürlich gerne geteilt werden.

2 Kommentare

Einen Kommentar hinzufügen

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert