Theoretische Informatik

Sortieralgorithmen

Hier gibt es einen allgemeinen Überblick zu Sortieralgorithmen und eine Erklärung zu den wichtigsten Begrifflichkeiten. Was steckt eigentlich wirklich hinter Sortierverfahren der Informatik und in welche zwei Typen lassen sie sich unterteilen? Was macht ein instabiles und stabiles Sortierverfahren aus? Diese Frage wird mit einem Beispiel einfach erklärt. Am Ende gibt es alle wichtigen Informationen zur Komplexität und die Eigenschaften verschiedener Sortieralgorithmen im Überblick.

Inhaltsübersicht

Sortieralgorithmus

Bei einem Sortieralgorithmus (auf Englisch sort algorithm oder sorting algorithm) handelt es sich in der Informatik um ein Sortierverfahren, der einen Array nach dem gewünschten Suchkriterium ordnen soll. Das funktioniert aber nur für eine streng schwache Ordnung, heißt entweder auf lexikografischer Basis – also nach Buchstaben bei einer Zeichenkette oder eben nummerisch – also nach Zahlen. Zur Umsetzung wird also eine Menge benötigt, die sortiert werden soll, die dabei aber auch gleichzeitig die Eingabe darstellt. Das Hauptziel eines Sortieralgorithmus ist zum einen, eine gegebene Menge effizient zu ordnen und zum anderen die sortierte Liste als Ausgabe zu übergeben.

Zwei Typen von Sortieralgorithmen

Sortierverfahren können sich allgemein durch die Basis der Arbeitsweise unterscheiden. Zum einen können Sortieralgorithmen vergleichsbasiert arbeiten oder eben nicht. Das heißt, dass ein Teil der Sortieralgorithmen Vergleiche von Elementen der Liste verwendet, um die Elemente entsprechend in die richtige Reihenfolge zu tauschen. Beim nicht vergleichsbasierten Verfahren liegt der Fokus auf der konditionierten Eingabe. Hier gibt es einen Überblick zur Aufteilung der Sortieralgorithmen beider Varianten – vergleichsbasiert und adressbasiert.

Sortieralgorithmen Sortierverfahren
direkt ins Video springen
Sortieralgorithmen

Wenn du mehr über die einzelnen Sortierverfahren wissen möchtest, schau dir doch einfach unsere Videos dazu an!  Dort findest du auch innerhalb unserer Beiträge zu den verschiedenen Sortieralgorithmen Java Quellcodes.

Stabile Sortierverfahren

Sortierverfahren können zusätzliche zwischen stabilem und instabilem Sortieren unterschieden werden. Stabile Sortierverfahren haben den Fokus, dass die Reihenfolge der Datensätze gleichbleibt, deren Sortierschlüssel auch gleich sind. Aber was heißt das jetzt genau?

Angenommen man möchte in einem Sportverein die alphabetisch geordnete Liste von Vereinsmitglieder nach dem Geburtsjahr sortieren. Dann sorgen stabile Sortierverfahren dafür, dass die Vereinsmitglieder mit gleichem Geburtsjahr, trotzdem noch nach der alphabetischen Reihenfolge sortiert bleiben. Das Verfahren sortiert sozusagen in erster Priorität nach dem Geburtsjahr und die 2. Priorität ist die alphabetische Reihenfolge. In diesem Fall steht also Alex vor Julian.

Stabiles Sortierverfahren nach Zahlen

1995 Alex 1995 Alex
1997 Christina 1995 Sebastian
1999 Hannah 1997 Christina
1997 Julian 1997 Julian
1995 Sebastian 1999 Hannah

Beispiele

Beispiele für ein stabiles Sortierverfahren sind:

Stabile Sortierverfahren, Stabiles Sortierverfahren
direkt ins Video springen
Stabile Sortierverfahren

Instabiles Sortierverfahren

Beim instabilem Sortierverfahren ist genau das Gegenteil der Fall. Nochmal zurück zu den Vereinsmitglieder. Hierbei können in diesem Fall verschiedene Endergebnisse nach einem Sortiervorgang vorkommen, daher auch die Bezeichnung instabil. Deshalb ist es auch möglich, dass Julian vor Alex steht und Sebastian vor Christina.

Instabile Sortierverfahren nach Zahlen

1995 Alex 1995 Alex 1995 Julian 1995 Alex 1995 Julian
1997 Christina 1995 Julian 1995 Alex 1995 Juian 1995 Alex
1999 Hannah 1997 Christina 1997 Christina 1997 Sebastian 1997 Sebastian
1995 Julian 1997 Sebastian 1997 Sebastian 1997 Christina 1997 Christina
1997 Sebastian 1999 Hannah 1999 Hannah 1999 Hannah 1999 Hannah

Beispiele

Beispiele für ein instabiles Sortierverfahren sind:

Instabiles Sortierverfahren, instabile Sortierverfahren
direkt ins Video springen
Instabiles Sortierverfahren

Komplexität

Wenn es um Sortierverfahren geht, kann man auch immer wieder auf den Begriff Komplexität stoßen. Dabei handelt es sich eigentlich nur um die Tatsache, dass die verschiedenen Algorithmen eben unterschiedlich effizient Datenmengen sortieren können. Welches Sortierverfahren im Endeffekt als „bester Sortieralgorithmus“ bezeichnet werden kann, muss immer individuell und situativ entschieden werden. Zwei Entscheidungsfaktoren bezüglich der Komplexität sind dabei die Sortieralgorithmen Laufzeit und der benötigte Speicherplatz.

Sortieralgorithmen Laufzeit

Die Effizienz der Sortieralgorithmen ist in den meisten Fällen vom Ausgangszustand abhängig – also wie ist die Datenmenge bei der Eingabe angeordnet. Dabei wird immer zwischen Best Case, Average Case und Worst Case unterschieden. Beispielsweise wenn die Liste schon von Beginn an sortiert ist, brauchen die meisten Sortieralgorithmen weniger Zeit zum Sortieren. Das wäre also entsprechend der beste Fall, da der Algorithmus dadurch noch effizienter ist.

Platzkomplexität – In-place

Noch dazu benötigen manche der Verfahren neben der gespeicherten Liste an Daten auch noch zusätzlichen Speicherplatz für Zwischenergebnisse.  Im Bezug darauf unterscheidet man auch, ob ein Sortierverfahren in-place arbeitet. Das heißt eigentlich nur, dass der zusätzliche Speicherbedarf unabhängig von der Anzahl der Datenmenge ist und deshalb meistens konstant und gering ist. Beim out-of-place ist es verständlicherweise genau das Gegenteil.

Sortieralgorithmen Vergleich

Hier kannst du dir jetzt noch alle Eigenschaften der verschiedenen Sortieralgorithmen im Bezug auf Komplexität und Stabilität im Vergleich ansehen.

Vergleichsbasiertes Sortieren

Sortieralgorithmus Best-Case Average-Case Worst-Case Stabil In-Place
Bubblesort O(n) O(n^2) O(n^2) Ja Ja
Heapsort O(n \cdot log(n)) O(n \cdot log(n)) O(n \cdot log(n)) Nein Ja
Insertionsort O(n) O(n^2) O(n^2) Ja Ja
Mergesort O(n \cdot log(n)) O(n \cdot log(n)) O(n \cdot log(n)) Ja Nein
Quicksort O(n \cdot log(n)) O(n \cdot log(n)) O(n^2) Nein Ja
Selectionsort O(n^2) O(n^2) O(n^2) Nein Ja
Shellsort O(n \cdot log(n)^2) O(n^1,25) Nein Ja

Überblick – Adressiertes Sortieren

Name Laufzeitkomplexität Speicherplatzkomplexität Stabil In-Place
Bucketsort O(n+k) O(n+k) Ja Nein
Countingsort O(n+k) O(n+k) Ja Nein
Radixsort O(n \cdot l) O(n) Ja Nein

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.