Sortieralgorithmen

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.

direkt ins Video springen

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

Beispiele

Beispiele für ein stabiles Sortierverfahren sind:

• Bubblesort
• Insertion Sort
• Mergesort
• Radix Sort

direkt ins Video springen

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

Beispiele

Beispiele für ein instabiles Sortierverfahren sind:

• Quicksort
• Heapsort
• Selectionsort
• Shellsort

direkt ins Video springen

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				Nein	Ja
Insertionsort				Ja	Ja
Mergesort				Ja	Nein
Quicksort				Nein	Ja
Selectionsort				Nein	Ja
Shellsort				Nein	Ja

Überblick – Adressiertes Sortieren

Name	Laufzeitkomplexität	Speicherplatzkomplexität	Stabil	In-Place
Bucketsort			Ja	Nein
Countingsort			Ja	Nein
Radixsort			Ja	Nein