Video anzeigen

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 — 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 — 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 — 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				Ja	Ja
Heapsort	$O(n \cdot log(n))$	$O(n \cdot log(n))$	$O(n \cdot log(n))$	Nein	Ja
Insertionsort				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))$		Nein	Ja
Selectionsort				Nein	Ja
Shellsort		$O(n \cdot log(n)^2)$		Nein	Ja

Überblick – Adressiertes Sortieren

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

Beliebte Inhalte aus dem Bereich Theoretische Informatik

Sortieralgorithmen

Bubblesort Klausuraufgabe

Quicksort Beispiel

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 .