Eine häufige Anwendung von Computern ist das Sortieren von großen Mengen an Daten. Um dem Computer das Sortieren beizubringen gibt es mehrere Algorithmen: Ich werde diese hier einmal mit Vor- und Nachteilen aufzählen.

Insert-Sort

Insert Sort ist wohl einer der langsamsten (wenn nicht der langsamste) Sortier-Algorithmus. Die grundlegende Idee ist, jedes Element eines Arrays zu betrachten. Ist dieses größer als das Element links von ihm, so werden die beiden vertauscht. Diese Schritte werden sooft wiederholt, bis der ganze Array aufsteigend sortiert ist.
Wie man unschwer erkennt, müssen Elemente bei diesem Algorithmus sehr oft vertauscht werden, was die Rechenzeit schnell aufbläht. Durch diese große Anzahl an Operationen ist die Komplexität dieses Algorithmus n² (n Anzahl der Datensätze). Daher auch der dritte Platz in diesem Vergleich. Bei steigender Datenmenge beweist sich InsertSort als sehr langsam und unpraktikabel.

Merge Sort

Der sogenannte Merge-Sort-Algorithmus ist mit seinen 0.0534 Sekunden deutlich schneller als Insert-Sort. Dies liegt daran, dass der Algorithmus nach dem divide and conquer-Prinzip (Teile und Herrsche) arbeitet: Bevor die Daten sortiert werden, werden sie in zwei möglichst gleichgroße Teile unterteilt, die dann erst sortiert und schließlich nach wieder nach dem Reisverschluss-Verfahren wieder gemischt werden. Diese Taktikt nennt man in der Programmierung rekursive Programmierung: Das Problem wird in Teil Probleme unterteilt, die effizienter zu lösen sind. MergeSort ist mit einer Komplexität von n*log₂n deutlich schneller als InsertSort.

Quick Sort

Zu guter Letzt der Gewinner dieses Vergleiches: Quicksort. Quicksort arbeitet sehr ähnlich wie Merge Sort, es unterteil ebenfalls die Datenmenge in kleinere Mengen und diese in wiederum kleinere, bis diese sortiert werden. Zwar hat QuickSort eigentlich die selbe Komplexität und damit Dauer wie MergeSort ( nämlich n*log₂n, wobei n die Anzahl der Datensätze ist), aber in der Praxis wird er als der schnellste Algorithmus gehandelt und demenstprechend oft genutzt. Besonders, wenn man statt des ersten Datensatzes einen zufälligen zum Vergleich wählt, steigt die Geschwindigkeit (siehe Code). Komischwerweise ähnelt die Geschwindigkeit sonst manchmal der sehr langsamen n².

Die Tests wurden mit 1024 zufälligen Zahlen ausgeführt, eigentlich ein relativ geringer Wert. Wenn man eine größere Menge wählt, wird besonders der Unterschied zu InsertSort noch deutlicher.
Da der gesamte Code von mir programmiert wurde, kann es gut sein, dass sich hier oder da ein kleiner Fehler eingeschlichen hat. Im wesentlichen habe ich diesen Code auch nicht auf Effizienz programmiert, sondern auf Lesbarkeit. Was haltet ihr von den Sortier-Algorithmen? Habe ich vielleicht euren Lieblings-Algorithmus vergessen?

[via]