Blogeintrag Juli 2018

Verschiedene Sortier Algorithmen  

 

Insertion Sort

Insertion Sort ist ein einfacher Sortieralgorithmus, der für kleine Listen und grossteils sortierte Listen relativ effizient ist und oft als Teil von komplizierteren Algorithmen verwendet wird. Er funktioniert, indem Elemente aus der Liste nacheinander genommen und in ihrer korrekten Position in eine neue sortierte Liste eingefügt werden. In Arrays können sich die neue Liste und die übrigen Elemente den Platz des Arrays teilen.

Selection Sort

 

Selection Sort ist eine direkte Vergleichssortierung. Es ist auf Grossen Listen relativ ineffizient und schneidet im Allgemeinen schlechter ab als das ähnliche Insertion sort. Die Selection Sort ist für ihre Einfachheit bekannt und weist auch Leistungsvorteile gegenüber komplizierteren Algorithmen in bestimmten Situationen auf.

Der Algorithmus findet den minimalen Wert, tauscht ihn mit dem Wert an der ersten Position und wiederholt diese Schritte für den Rest der Liste. Es macht nicht mehr als n Swaps und ist daher nützlich, wenn möglichst wenige Swaps gemacht werden sollen.

 

Bubble Sort 

 

Beim Bubble sort wird in einer Reihe von Elementen nach und nach jedes mit dem Nachbar verglichen und wenn nötig getauscht. Da nach jedem Durchlauf der grösste Wert ganz rechts ist, wird auch entsprechend nach jedem Durchlauf die Anzahl noch zu sortierender elemente um 1 verringert.

Shell Sort

shell Sort verbessert die Sortierung, indem es um mehr als eine Position nach dem anderen versetzt. Shell Sort ist optimal für Daten, mit nur wenigen Elementen die sich nicht in der richtigen Position befinden. In diesem fall werden die einzelnen Elemente weit entfernt sortiert und die Lücke zwischen den zu sortierenden Elementen schrittweise verkleinert, was die endgültige Sortierung viel schneller macht.

Merge Sort

Merge sort nutzt die Möglichkeit, bereits sortierte Listen in eine neue sortierte Liste zusammenzufassen. Es beginnt damit immer zwei Elemente zu vergleichen (d.h. 1 mit 2, dann 3 mit 4 ...) und tauscht sie aus, wenn das erste nach dem zweiten kommen sollte. Es führt dann jede der resultierenden Listen von zwei in Listen von vier zusammen, führt dann diese Listen von vier zusammen und so weiter; bis zuletzt zwei Listen in der endgültigen sortierten Liste zusammengeführt werden. dieser Algorithmus ist gut auch für grosse Listen anwendbar.

Heap Sort

 

Das Heap sort ist ein relativ komplexes verfahren das als verbesserung des Selection Sort angesehen werden kann. Der Algorithmus arbeitet mit einer Sruktur in welcher immer das Grösste (oder Kleinste) Element nach oben Verschoben und anschliessend Einsortiert wird.

Quick Sort

 

Um ein Array mit Quick Sort zu sortieren, wird ein Element ausgewählt, das Pivot genannt wird. Alle Elemente, die kleiner als der Pivot sind, werden davor bewegt und alle größeren Elemente werden dahinter verschoben. Die kleineren und größeren Unterlisten werden dann rekursiv sortiert. Quick Sort ist eine der beliebtesten Sortieralgorithmen, und in vielen Standardprogrammierbibliotheken verfügbar.Der wichtige Vorbehalt gegenüber Quicksort ist seine Worst-Case-Leistung. Diese tritt ein wenn als Pivot Element das Grösste oder Kleinste Element Verwendet wird, da in diesem Fall kein Vorteil erzielt wird.

 
Die Sortier Algorithmen sind unter diesem Link noch mit einer Kurzen Animation dargestellt.