Archiv: onli blogging

Der Quicksort ist vom Prinzip schon sehr effektiv. Trotzdem kann er in natürlich optimiert werden, um den Wort-Case seltener eintreten zu lassen und die reale Performance zu erhöhen - nur wie? Welche Verfahren sind praktikabel, welche Kleinigkeiten kann man beachten?

Ich muss da selbst noch einiges lernen. Was mir aber bei meinen Versuchen bisher aufgefallen ist:

1. Kleinigkeiten nützen schon etwas. Wenn man nicht das mittlere Element als Pivot, sondern das linke oder das rechte wählt, dann kann man den jeweiligen Cursor auch links bzw. rechts vom Pivot ansetzen.

2. Noch eine Kleinigkeit: Beim Tauschen darauf achten, dass die zu tauschenden Elemente nicht sowieso schon gleich sind (evtl. ist das auch schlecht: kostet die Abfrage mehr Leistung als das unnötige Tauschen?)

3. Es gibt eine (relativ) naive Implementierung, bei der das linke, das mittlere und das rechte Element verglichen werden und der Mittelwert als Pivot gewählt wird. Wenn man die sowieso manuell betrachtet, kann man sie auch sortiert zurückschreiben: das kleinste nach links, das größte nach rechts, das Pivot in die Mitte.
Meinen bisherigen Tests nach hilft das enorm bei halbwegs geordneten Listen, schadet aber ein kleines bißchen bei komplett ungeordneten Zahlenabfolgen.

4. Wenn nur noch zwei Elemente in der zu sortierenden Liste sind, sollte das linke zum Pivot werden. Das kann aber natürlich auch eine Macke in meiner Implementation sein.

Noch testen will ich, wie es sich auswirkt, wenn man mehrere Threads nutzt und wie man das am besten anstellt.

Und sowieso: Ist es in der Realität nicht eher besser, auf die Kleinigkeiten zu verzichten und sich auf die Wahl eines guten Pivots zu beschränken, weil so Abfragen gespart werden - oder wiegen die gesparten Arrayzugriffe das wieder auf?