Vergleich von Sortieralgorithmen

Inhalt

1 Das Sortierproblem

2 Allgemeines zu Sortieralgorithmen

3 Analyse der drei Sortieralgorithmen
3.1 Enhanced-Bubblesort
3.2 Shellsort / Insertionsort
3.3 Tim Sort

4 Performancemessungen
4.1 Durchführung der Tests
4.2 Testergebnisse
4.3 Auswertung

5 Fazit / Ausblick

6 Danksagung

Literatur

A Python-Scripte zum Durchführen der Performancetests

В Vollständige Python- Implementierung von Timsort

Zusammenfassung Diese Arbeit beschäftigt sich mit dem Sortierpro­blem und entsprechenden algorithmischen Lösungsmöglichkeiten. An­hand der Algorithmen Enhanced-Bubblesort, Enhanced-Shellsort und dem auf Mergesort basierenden Timsort wird aufgezeigt, wie grundle­gende Prinzipien in den letzten Jahren erweitert bzw. optimiert wurden. Darüber hinaus wurde eine empirische Untersuchung hinsichtlich der Laufzeiten der Algorithmen durchgeführt, um Aussagen darüber tref­fen zu können, in wie weit die Verbesserungsbemühungen von Erfolg gekrönt worden sind. Weiterhin hat es sich herausgestellt, dass es in der verwendeten Veröffentlichung [Alnihoud und Mansi(2010)], welcher der Enhanced-Bubblesort-Algorithmus zu Grunde liegt, zu Fehlaussagen ge­kommen ist. Diese werden aufgeführt und korrigiert.

1 Das Sortierproblem

Insbesondere für die Entwicklung von effizienten Suchalgorithmen ist es erfor­derlich, dass sich im Computer gespeicherte Daten in einer definierten Ordnung befinden. Nur so kann der Suchalgorithmus Rückschlüsse auf die zu erwartende Position des gesucheten Datensatzes ziehen. Gelingt dies nicht muss auf einen zeitraubenden Vergleich mit - im schlechtesten Falle - jedem vorhandenen Da­tendatensatz zurückgegriffen werden. Suchanfragen, wie beispielsweise bei der weltweit bekannten Suchmaschine Google, wären vermutlich nicht oder nur unter exorbitant hohen Kosten in den Sekundenbruchteilen möglich, die wir gewohnt sind. Dieses Daten in eine definierte Ordnung bringen, wird im Allgemeinen als Sortieren bezeichnet. Im angesprochenen Fall einer Suchmaschine müssen Daten nur sortiert werden, wenn neue Daten, wie Webseiten, hinzukommen oder sich ändern. Dies geschieht deutlich seltener als Suchanfragen ausgeführt werden. Dennoch ist auch hier die Sortiergeschwindigkeit ein beachtenswerter Faktor, der sich durch Anforderungen wie der Echtzeitsuche in sozialen Netzwerkdiens­ten wie Twitter oder Facebook noch verschärft. Sortieren gehört nicht nur in der Suche, sondern auch in vielen Anwendungen bis hin zur Dateiorganisation im Betriebsssystem zum Standardrepertoire der Informationsverarbeitung und das nicht erst seit Kurzem. So ist es also nicht verwunderlich, dass sich vie­le Informatiker seien es Theoretiker oder Praktiker mit dem Problem und den dazugehörigen Facetten der Datensortierung auseinandergesetzt haben, ausein­andersetzen und auch auseinandersetzen werden.

2 Allgemeines zu Sortieralgorithmen

Generell ist es bei der Analyse von Sortieralgorithmen natürlich von Interesse wie schnell sie in der Lage sind ihre Aufgabe zu lösen die Eingabedaten in den gewünschten sortierten Zustand zu bringen. In der Regel werden Algorithmen durch mathematische Analyse - unabhängig von der verwendeten Hardware - in der О-Notation (siehe [Sedgewick(2002), s. 63]) für den Worst-Case, den schlech­testen Fall, den Best-Case, den Ideal-Fall, und den Average-Case, der im Durch­schnitt zu erwarteten Laufzeit, dargestellt. Aber auch andere Aspekte sind von Interesse:

Stabilität Ist ein Sortierverfahren stabil bedeutet dies per Definition, dass sich die Reihenfolge gleicher Elemente relativ zueinander nicht ändert. Wenn man die Schlüssel von mehreren Elementen sortiert und es zwei Elemente A und в gibt, die ursprünglich hintereinander stehen und beide den selben Schlüssel haben, dann muss A nach Durchführung der Sortierung immer noch vor В platziert sein, damit der Algorithmus als stabil bezeichnet werden kann. [Sedgewick(2002), s. 276]

adaptiv VS. nicht-adaptiv Es wird zwischen nicht-adaptiven und adaptiven Sortieralgorithmen unterschieden. Nicht-adaptive Sortieralgorithmen arbei­ten - völlig unahängig von der Beschaffenheit der Eingabedaten - stets die selbe Befehlsfolge ab, während adaptive Sortieralgorithmen - in Abhängig­keit der Eingabedaten - unterschiedliche Befehlssequenzen ausführen. [Sedgewick(2002), s. 275].

extern VS. intern Von einem internen Sortierverfahren spricht man, wenn da­von ausgegangen wird, dass auf jedes Element jederzeit ohne besondere Vor­kehrungen zugegriffen werden kann. Dies geschieht in der Regel, indem die gesamte Eingabedatenmenge in den Hauptspeicher geladen wird. Externe Sortierverfahren berücksichtigen hingegen bei entsprechend großen Daten­mengen, Speichersysteme wie Festplatten einzubeziehen. Dies erweitert die Anforderungen, da hier ein Direktzugriff nicht ohne weiteres möglich ist. [Sedgewick(2002), s. 272] Bei den in dieser Arbeit betrachteten Sortieralgo- ritInnen handelt es sich ausschließlich um interne Sortierverfahren, in-place / in situ Bei internen Sortieralgorithmen müssen zumindest die Ein­gabedaten im Speicher gehalten werden. Desweiteren kann es jedoch - je nach Algorithmus - Vorkommen, dass darüber hinaus noch weitere Informa­tionen im Speicher abgelegt werden. Ein Algorithmus arbeitet in-place auch in situ genannt, wenn der über die Speicherung von Eingabedaten hinaus benötigte Speicherverbrauch unabhängig von der Menge der Eingabedaten ist. Dies bedeutet, dass der Algorithmus - abgesehen von Funktionsaufrufen und Hilfsvariablen - im Bereich der Eingabedaten arbeitet, nicht aber bspw. eine weitere Liste mit Kopien der Eingabedaten erzeugt.

3 Analyse der drei Sortieralgorithmen

Im Folgenden werden die Sortieralgorithmen Enhanced-Bubblesort, Enhanced- Shellsort sowie Timsort analysiert. Alle drei Algorithmen dienen als Beispiel, wie bereits bekannte Sortierprinzipien verändert wurden, um in erster Linie die Geschwindigkeit des Sortiervorgangs zu verbessern. Die Analysen beziehen sich hierbei exemplarisch auf die Sortierung von Arrays, auch wenn alle Algorithmen - mit geringen Anpassungen - auch verkettete Listen sortieren könnten. Die Analyse umfasst die Erläuterung der verwendeten Idee zur Vorgehensweise und deren Herkunft, sowie nach Möglichkeit auch eine mathematische Beschreibung des zu erwartenden Aufwand an durchzuführenden Rechenoperationen. Für je­den Algorithmus wird ein kurzes Zwischenfazit gezogen, um dessen Stärken und Schwächen zu thematisieren.

3.1 Enhanced-Bubblesort

Der Sortieralgorithmus Enhanced-Bubblesort wurde im Jahre 2010 im Rah­men der Arbeit [Alnihoud und Mansi(2010)] veröffentlicht. Der Name Enhanced- Bubblesort soll ihn als Erweiterung zum Bubblesort-Algorithmus verstanden wis­sen [Alnihoud und Mansi(2010), s.58]. Allerdings zeigt sich bei Betrachtung der Funktionsweise von Enhanced-Bubblesort, dass größere Ähnlichkeiten zum in [Sedgewick(2002), s. 278] beschriebenen Selectionsort-Algorithmus bestehen.

Selectionsort sucht das kleinste Element einer Eingabemenge und tauscht dieses mit dem ersten Element der Eingabe aus. Dies geschieht bei verkleinerten Such­bereich so lange bis sich alle Elemente - im Hinblick auf die Sortierung - an der korrekten Position befinden.

Bei Bubblesort hingegen werden benachbarte Elemente so lange vertauscht, bis sich die Menge der Elemente in sortierter Reihenfolge befindet [Sedgewick(2002), s. 282]

Die Funktionsweise von Enhanced Bubble Sort Enhanced Bubble Sort durchläuft die gegebene Liste zunächst vollständig, um das größte und das kleins­te Element zu bestimmen (Siehe Beispielimplementierung 3.1 Zeile 8-14). Das kleinste gefundene Element wird mit dem ersten Element der Eingabedaten ge­tauscht und das größte mit dem letzten Element (3.1 Zeile 15-37). Anschließend wird der Arbeitsbereich an beiden Rändern jeweils um ein Element verkleinert, da sich die beiden äußeren Elemente bereits an der korrekten Position befin­den (3.1 Zeile 38-40)- Die Randelemente sind nun korrekt platziert, da sich das kleinste Element einer sortierten Liste - per Definition - an der ersten Stelle befindet. Analog hierzu befindet sich das größte Element an der letzten Stelle.

Der sinifikante Unterschied zum Selectionsort-Algorithmus ist, dass in einem Durchlauf nicht nur das kleinste Element, sondern auch das größte Element be­stimmt und bewegt wird. Das sonstige Vorgehen ist identisch.

Der Arbeitsbereich wird pro Durchgang jeweils um zwei Elemente verkleinert und durchsucht, bis die komplette Liste sortiert ist. Bezeichnen wir die Anzahlder Eingabeelemente als n. Der Arbeitsbereich wird im zweiten Durchgang auf n — 2 Elemente beschränkt, im dritten Durchgang sind es ??4 — ׳ Elemente. Insge­samt beläuft sich die Anzahl der Durchgänge auf: 7J. Bezeichnen wir die Anzahl der benötigten Vergleiche der Suche nach dem kleinsten und größten Element mit j. г sei die Nummer des aktuellen Durchgangs beginnend bei 0. Somit ergibt sich für die Gesamtanzahl der benötigten Vergleiche im Enhanced-Bubblesort- Algorithmus, falls es sich bei n um eine gerade Zahl handelt:

Abbildung in dieser Leseprobe nicht enthalten

Mithilfe der Gaußschen Summenformel - die in [Teschi und Teschl(2008), S.47] mittels Induktionsprinzip bewiesen wird - können wir die Gleichung vereinfa­chen:

Abbildung in dieser Leseprobe nicht enthalten

Bei einer ungeraden Anzahl von Elementen muss die mathematische Beschrei­bung dahingehend angepasst werden, dass die Anzahl der Durchläufe zur nächs­ten geraden Anzahl erhöht wird. Dies gilt, da der Arbeitsbereich paarweise ver­kleinert wird und das letzte Element trotz fehlenden Partnerelementes dennoch bearbeitet wird. Somit gilt für die Anzahl der Durchgänge: Weiterhin gilt, dass ein Arbeitsbereich mit einer ungeraden Anzahl von Elementen der um zwei Elemente verkleinert wird, immer noch eine ungerade Anzahl von Elementen besitzt. Somit gilt für die zu durchsuchenden Elemente im i. Durchgang:

Abbildung in dieser Leseprobe nicht enthalten

Für die Gesamtanzahl der Vergleichsoperationen bei einer ungeraden Anzahl von Eingabeelementen ergibt sich:

Abbildung in dieser Leseprobe nicht enthalten

Die obere Schranke о für diesen Algorithmus liegt daher bei

Abbildung in dieser Leseprobe nicht enthalten

Zwischen Worst-, Average- und Best-Case muss nicht unterschieden werden, da der Algorithmus in jedem Fall, unabhängig von der Beschaffenheit der Eingabe­daten, die entsprechende Anzahl von Operationen ausführt, je nachdem ob es sich um eine gerade Anzahl von Eingabedaten oder eine ungerade Anzahl Iran- delt.

Die mathematische Einordnung des Enhanced-Bubblesort-Algorithmus der Au­toren bzgl. der О-Notation in [Alnihoud und Mansi(2010)] , dass die obere Schraň- ke bei 0(11 lg n) hegt, ist somit nicht korrekt.

Implementierung von Enhanced Bubble Sort Entgegen der Pseudocode­Implementierung aus der Quelle [Alnihoud und Mansi(2010)], wurde eine Schlei­fe anstatt der Rekursion verwendet, um aufgrund des begrenzten Heap Speichers größere Testdaten verwenden zu können.

Abbildung in dieser Leseprobe nicht enthalten

Listing 1.1. Enhanced Bubblesort

Zwischenfazit Die durch die Präsentation von Enhanced-Bubblesort geweckten Erwartungen einer oberen Schranke von 0(11 lg n) wurden nicht erfüllt. Von der Namensgebung her, wäre die Bezeichnung Enhanced-Shellsort angebrachter, da sich beide Algorithmen nur dadurch unterscheiden, dass Enhanced-Bubblesort pro Durchgang das größte und das kleinste Element bestimmt und positioniert,während Enhanced-Shellsort nur das kleinste Element beachtet. In beiden Algo­rithmen wird ein Arbeitsbereich durchsucht. Selectionsort verkleinert diesen pro Durchgang nur um ein Element, während Enhanced-Bubblesort den zu durch­suchenden Arbeitsbereich um zwei Elemente verkleinert. Enhanced-Bubblesort benötigt also nur halb so viele Schleifendurchgänge wie Selectionsort. Allerdings kann man dennoch nicht mit einer Verdoppelung der Geschwindigkeit rechnen, da Enhanced-Bubblesort während der Suche jeweils ein Objekt mit zwei Hilfs­variablen vergleicht (3.1 Zeile 9-14), während Selectionsort nur einen Vergleich durchführt.

3.2 Shellsort / Insertionsort

Der Shellsort-Algorithmus basiert auf der Idee des Insertionsort-Algorithmus, zu deutsch: Sortieren durch Einfügen. Beschäftigten wir uns daher zunächst mit dem Prinzip von Insertionsort:

Insertionsort Stellen wir uns einen Kartenspieler vor, der - wie in vielen Spie­len üblich - eine Anzahl von Karten erhält. Diese möchte er in eine Ordnung bringen. Wie geht er am geschicktesten vor? Er könnte beispielsweise eine der Karten in die Hand nehmen und sie von links beginnend mit den verbleibenden Karten so lange vergleichen bis er eine Karte findet, die laut der Ordnung größer als die Karte ist, die er in der Hand hält. Genau vor dieser größeren Karte steckt er die in der Hand gehaltene Karte wieder in sein Blatt. Er fügt sie ein, woher auch der Name Insertionsort herrührt. Dann nimmt er wieder eine Karte in die Hand und führt diesen Vorgang so lange durch, bis er alle Karten aufgenommen hat.

In einer Implementierung auf dem Computer, wie in der Beispielimplementierung 3.2, sind Arrays allerdings nicht so flexibel wie eine Hand von Karten. Außer­dem soll Insertion Sort in-place arbeiten, also auf der Eingabemenge arbeiten, so dass keine zweite Liste, wo Elemente in der korrekten Reihenfolge eingefügt werden könnten, erzeugt werden darf. Daher muss zum Einfügen zunächst Platz geschaffen werden, in dem alle größeren Elemente nach rechts geschoben werden, um das Element an der freiwerdenden Position einfiigen zu können (Beispielim­plementierung 3.2 Zeile 17-19) [Sedgewick(2002), S.279]. In Betrachtung der zu erwartenden Sortiergeschwindigkeit, ist es bei Insertionsort problematisch, dass nur benachbarte Elemente miteinander ausgetauscht werden. Liegt eine genau umgekehrt sortierte Liste vor, beispielsweise: 10 987654321, wären im ersten Durchgang zehn Schritte nötig um das Element 1 an die korrekte Position zu bewegen. Im zweiten Durchgang sind es neun um das Element 2 an die zweite Stelle zu bringen usw.

Abbildung in dieser Leseprobe nicht enthalten

Insgesamt gilt für den Aufwand dieses Worst-Case Szenarios:

[Teschi und Teschl(2008), s.47]

Im Best-Case Szenario ist das Array bereits sortiert und es sind in der Beispielimplementierung n+(n-l) = 2n-l Schritte notwendig.

Librarysort Ein Ansatz Insertionsort zu verbessern trägt den Namen Libra­rysort. Hiebei werden zwischen den Elementen Lücken gelassen werden, um bei einer Sortierung nur eine möglichst geringe Anzahl von Elementen ver­schieben zu müssen, da das einzusortierende Element im Idealfall direkt in der passenden Lücke platziert werden kann. Library Sort ist durch dieses Ver­fahren in der Tat schneller als Insertionsort, allerdings wird durch die Lücken auch mehr Arbeitsspeicher benötigt. Daher arbeitet Librarysort nicht in-place. [Bender u. a.(2006)Bender, Farach-Colton und Mosteiro]

Shellsort Donald L. Shell entwickelte im Jahre 1959 den Shellsort-Algorithmus, welcher die Beschränkung des Austausch weit entfernter Elemente seitens Inser­tionsort ebenfalls umgeht, allerdings ohne zusätzlichen Speicherbedarf wie Li­brarysort. Shellsort arbeitet also eben so wie Insertionsort in-place [Shell(1959)] : Wie nun die Distanzen über welche Elemente ausgetauscht werden können er­höhen? Der Shellsort-Algorithmus führt den Insertionsort-Algorithmus in seiner ursprünglichen Form mehrmals auf der Eingabedatenmenge aus. Hierbei gilt al­lerdings, dass die einzelnen Insertion Sort Aufrufe nur eine Teilmenge sortieren. Und zwar eine Teilmenge aus Elementen, die einen definierten Abstand zuein­ander haben, der sich in jedem Durchgang verkleinert. Ein Beispiel:

Gegeben sei:

[4,7,8,11,5,3,1,9,3,4]

Sei der Abstand der Elemente zueinander zwei. Somit würde ein Insertionsort über die folgenden Elemente ausgeführt werden:

[4,11,1,4]

dies würde dazu führen, dass die Liste nun wie folgt aussieht:

[1,7,8,4,5,3,4,9,3,11]

es wurde somit das 1., das 4., das 7. und das 10. Element sortiert. Man kann die Datei als 3-sortiert bezeichnen, da jedes dritte Element sortiert ist. Im nächs­ten Durchgang wird die Größe der Abstände weiter verkleinert. Betrachten wir einen Abstand von 1. Somit würde Insertionsort nun die folgenden Elemente bearbeiten:

[1,8, 5,4,3]

nach diesem Durchgang sieht die Liste dann wie folgt aus:

[1,7,3,4,4,3,5,9,8,11]

Das Ergebnis hat sich einer tatsächlichen Sortierung nun sichtbar angenähert. Durch die Abstände ist es Shellsort möglich, Elemente direkt über größere Di­stanzen zu bewegen. Nachteilig ist, dass Shellsort nicht stabil agiert, da es durch das Überspringen von Elementen Vorkommen kann, dass ein Element vor einem anderen Element mit dem gleichen Schlüssel plaziert werden kann, ohne das die ursprüngliche Reihenfolge beachtet wird. Unabhängig davon, wie die Ab­standsfolgen gewählt werden, beträgt der Abstand im letzten Durchgang immer Eins. Dies führt dazu, dass ein Insertionsort Algorithmus auf den gesamten Ein­gabedaten operiert. Dieser profitiert nun erheblich von den vorausgegangenen Teilsortierungen. Im klassischem Shell Sort, wie in [Sedgewick(2002), s. 291] be­schrieben, wird die Abstandsfolge “ f > 3/7121*1,3 + 364*1,3 + 1093 *3 ...1+ ׳ + 1,3*40+ 1,3* 13 + 1,3*4 + 1,3*1 + 1,1” (mit h=l und n = Anzahl der Einga­beelemente) verwendet (Siehe Beispielimplementierung 3.2 Zeile 2-4 u. Zeile 13). Robert Sedgewick erläutert, dass die Wahl einer Abstandsfolge in der Praxis die Geschwindigkeit um höchstens 25% erhöhen kann [Sedgewick(2002), S.291]. In [Sedgewick(2002), S.294] erläutert Sedgewick weiterhin, dass Shell Sort für die oben genannte Folge weniger als

Abbildung in dieser Leseprobe nicht enthalten

Vergleiche benötigt. Ursprünglich schlug Shell die Zweier-Potenzen als Abstands­folge vor, allerdings führt diese Folge in vielen Fällen zu schlechten Ergebnissen, da hier Elemente an ungeraden Positionen nur im letzten Durchgang mit Eie- menten an geraden Positionen verglichen werden.[Sedgewick(2002), S.292],

Enhanced Shell Sort In [Shahzad und Afzal(2007)] wird eine Verbesserung des Shellsort-Algorithmus mit der Abstandsfolge “.. .40 13 4 1” vorgestellt und diskutiert. Die Autoren legen mit empirischen Überlegungen und Versuchen dar, dass durch ein Verwenden einer Abstandsfolge die Eingabemenge halbiert, dies dann wiederum halbiert usw. eine deutliche Senkung der nötigen Vertauschungs­operationen bietet (Siehe Beispielimplementierung 3.2 Zeile 4 u. Zeile 13). Die Autoren kommen zu dem Schluss, dass die Anzahl der nötigen Vertauschungs­operationen gegenüber der bisher verwendeten Abstandsfolge halbiert wird. Dies führen sie unter anderem darauf zurück, dass die vorgeschlagende Abstandsfolge besser auf die Eingabemenge skaliert, indem es bei kleinen Eingabemengen zu vielen Durchgängen kommt, dies aber bei größeren Eingabemengen nicht linear fortgeführt wird. Bei 100 Elementen würde diese Abstandsfolge Z.B. wie folgt lauten:

50,25,13,7,4,2,1

die Abstandsfolge des ursprünglichen Shellsort-Algorithmus hingegen:

13,4,1

Durch Aufrunden, wird das bereits bzgl. Zweierpotenzen betrachtete Problem umgangen, dass bei einer nur aus geraden Zahlen bestehenden Abstandsfolge bis zum letzten Durchgang nur Elemente an geraden Positionen miteinander vertauscht werden.

Beispielimplementierungen Es folgen Beispielimplementierungen der erläu­terten Algorithmen in der Programmiersprache Python:

Abbildung in dieser Leseprobe nicht enthalten

Listing 1.2. Insertion Sort

Die Implementierung basiert auf [Sedgewick(2002), s. 281]

Abbildung in dieser Leseprobe nicht enthalten

Listing 1.3. der klassische Shellsort

Die Implementierung basiert auf [Sedgewick(2002), s. 291]

Abbildung in dieser Leseprobe nicht enthalten

Listing 1.4. Enhanced Shellsort Die Implementierung basiert auf [Shahzad und Afzal(2007)]

Zwischenfazit Bei Shellsort handelt es sich um einen einfach zu implementie­renden Algorithmus, der zwar nicht stabil ist, aber in place arbeitet. Selbst für größere Dateien erzielt er noch akzeptable Laufzeiten [Sedgewick(2002), s.297].

Hervorzuheben ist außerdem, dass er trotz der wenigen Zeilen Quelltext eine bemerkenswerte Komplexität zeigt. Dies zeigt sich vor allem in der Diskussion zur optimalen Wahl der Abstandsfolge, die auch im Jahr 2007 noch Relevanz hat, obwohl dieser Algorithmus bereits seit dem Jahre 1959 existiert.

3.3 Tim Sort

Tim Sort wurde im Jahre 2002 von Tim Peters entwickelt und ist seit Version 2.3 der von Python intern verwendete Sortieralgorithmus. [Peters(2002)] Außerdem wird der Algorithmus in der kommenden Version 7 der Java SE Distribution als auch in der Java Implementierung von Googles Handybetriebssystem Android zum Sortieren von Arrays eingesetzt, [jjb (Nickname) (2009)]

Es werden zwei der bereits bekannten Sortiertalgorithmen in abgewandelter und erweiterter Form eingesetzt:

Insertionsort, welches bereits im Zuge des Shellsortalgorithmus betrachtet wurde und Mergesort, dessen Funktionsprinzip kurz erläutert wird.

Mergesort Die Grundidee in Mergesort ist das Prinzip des Teilens und Herr­Sehens. Dieses Prinzip beruht darauf, dass komplexe Probleme so lange in Teil­probleme zerlegt werden bis diese lösbar sind. Anschließend wird aus den gelösten Teilproblem eine Lösung des komplexen Gesamptproblemes erzeugt. Im Fall der zu sortierenden Eingabedaten werden diese so lange geteilt, bis die einzelnen Teile nur noch aus einem Element bestehen. Diese werden so wieder zusammen­gesetzt, dass eine sortierte Liste entsteht.

Die Funktionsweise von Tim Sort Ein zentrales Optimierungsmerkmal von Tim Sort ist das Identifizieren von bereits sortierten Teilbereichen der Einga­bemenge. Hieraus wird ein Nutzen gezogen, da diese Bereiche in sich selbst nicht umstrukturiert werden müssen. Ein großer bereits sortierter Teilbereich der identifiziert wurde, kann somit einige Rechen- und Speicheroperationen ein­sparen, in dem er als Block und wie ein einzelnes Element behandelt wird. In der Beispielimplementierung begegnet uns diese Strategie in zwei Funktionen: count Run AndMake Ascending prüft eine Teilmenge vom ersten Element an auf eine bestehende Sortierung. Hiebei wird entweder die gesamte Teilmenge als sortiert erkannt oder ein Teilbereich vom ersten bis zum dem darauf folgenden Element, welches nicht in die Sortierung passt. Dies gilt auch für umgekehrt sortierte Teilmengen, wobei diese explizit in eine sortierte Reihenfolge gebracht werden (Funktion rever se Range).

In gallopLeft und gallopRight ist das Galopping Verfahren, welches im Zuge der Verschmelzungsoperationen noch detailierter betrachtet wird,implementiert. Das Galopping Verfahren nutzt bereits sortierte Teilbereiche um das Zusammen­führen zweier Teilmengen zu beschleunigen.

Ein weiteres Merkmal dieses Algorithmus ist die Kombination eines Insertion­Sort- und eines Mergesort-Verfahrens.

Bei der Betrachtung von Insertionsort wurde erläutert, dass es zu den Schwa­chen dieses Algorithmus gehört, dass Elemente nicht über große Distanzen aus­getauscht werden können. Dies wird sich vor allem bei zwei Szenarien negativ aus: Bei umgekehrt sortierten Daten und bei großen Datenmengen. Denn mit der Größe der Datenmenge wächst die maximale Distanz, die ein einzelnes Eie- ment überbrücken muss, um an seine - laut der Sortierung - korrekte Position zu gelangen.

Für Mergesort hingegen stellen große Datenmengen keine spezielle Problema­tik da, wogegen sich bei kleinen Datenmengen der Overhead an Operationen wie Fallunterscheidungen bezüglich der Zusammenführung der Teilmengen negativ auswirkt.

Tim Sort macht sich die so eben erläuterten Eigenschaften der beiden Algo­rithmen zu Nutze: Kleine Datenmengen werden direkt mit Insertionsort sortiert (Funktion binary Sort). Große Datenmengen werden, wie es für Mergesort üb­lieh ist geteilt. Allerdings nicht wie im klassischen Mergesort so lange, bis die entstandenen Teilmengen nur aus einen Element bestehen, sondern bis zu einer definierten Mindestgröße. Die so entstandenen Teilmengen werden nun durch Insertionsort sortiert. Das Mergesort Verfahren wurde somit abgekürzt und es müssen nicht mehr einzelne Elemente so lange verbunden werden, bis eine Sor­tierung erreicht ist, sondern größere Teilmengen. Die angedeutete Mindestgröße, anhand der zwischen dem Einsatz von Tim Sort und Insertionsort unterschieden wird, wurde von Tim Peters experimentell festgelegt.

Tim Sort verwendet adaptiv zwei Verfahren bzw. Modi um zwei sortierte Mengen zu verschmelzen: “One pair at a time” und “Galloping”. Bevor es allerdings zur eigentlichen Verschmelzung kommt führt Tim Sort auf den Mengen A und в je­weils eine binäre Suche (Siehe [Sedgewick(2002), s. 74]) durch. Es wird bestimmt an welcher Stelle das erste Element von в in der Menge A eingeordnet werden müsste. Alle Elemente in A vor dieser Position können vernachlässigt werden, da sie sich bereits an der korrekten Position befinden. Weiterhin wird gesucht, wo das letzte Element von A in der Menge в eingeordnet werden müsste. Hier gilt, dass alle Elemente in в nach dieser Position ebenfalls vernachlässigt werden können. Im schlimmsten Fall hat man hierdurch den maximalen Aufwand für die binären Suchen:

19(A) + lg(B) + 2

[Sedgewick(2002), s. 74]

durchgeführt und nichts gewonnen. Im besten Fall allerdings kann man durch die­se Vorgehensweise den Arbeitsbereich für den Verschmelzungsvorgang deutlich verkleinern, was sowohl den zusätzlich benötigten Speicher als auch die Laufzeit deutlich verkürzt.

Bei “One pair at a time” deutet der Name auf die Vorgehensweise hin, es wird für jede Menge A und в ein Index geführt, der links beim kleinsten Element an­fängt. Die beiden Elemente, auf die der jeweilige Index zeigt, werden paarweise miteinander vergleichen. Das laut Ordnung kleinere Element wird in die neue Liste übernommen und der entsprechende Index erhöht. Hierbei wird die klei­nere der beiden Mengen in eine temporäre Liste kopiert, so dass der ehemalige Bereich von A und в umorganisiert werden kann. Ein Verschmelzen der Mengen A und В benötigt daher min(A,B) zusätzlichen Speicherplatz allerdings nur für den Zeitraum der Verschmelzung. In Abbildung 1 sehen wir die Verschmelzung

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 1. “One pair at a time” Modus - Zusammenführen zweier Mengen

zweier Beispielmengen. Zunächst wird 1 mit der 2 verglichen wobei 1 in der Er­gebnismenge platziert wird. Anschließend 2 mit der 4, 2 wird platziert, 2 mit der 3, 3 wird platziert und 4 mit der 5, die 4 wird platziert...

Generell gilt, dass eine Verschmelzung zweier Listen auf diese Weise genau A+B- 1 Vergleiche benötigt. Der Aufwand ist linear abhängig von der Größe beider Listen.

Der “Galopping Modus”, wird verwendet um, innerhalb der beiden Eingabemen­gen A und B, Blöcke zu identifizieren, die in sich nicht gemischt werden müssen. Es handelt sich hierbei somit um Teilmengen, für die es in der jeweils anderen Menge keine Elemente gibt, die von der Ordnung her zwischen das erste und das letzte Element dieser Teilmenge gehören. Der Vorteil solcher Blöcke ist, dass man diese als ganzes an die richtige Position bewegen kann, ohne einzelne Eie- mente des Blockes mit der anderen Liste vergleichen zu müssen, was bei großen Blöcken viele Rechenoperationen sparen kann.

Während generell der “One pair at a time” Modus verwendet wird, verfolgt

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 2. “Galopping” Modus - Zusammenführen zweier Mengen

dieser über eine Zählvariable, wie lange es her ist, dass ein Element aus einer anderen Menge verwendet wurde. Ein Beispiel:

A : [1,2,3,4,5,6,11] В : [7,8,9,10,12]

Die Elemente 1 bis 6 aus der Menge A werden alle jeweils im Vergleich mit der 7 als das kleinere Element bestimmt. Wenn der Algorithmus bei dem Element 4 angekommen ist, ist dies das vierte Element welches ohne Unterbrechung aus der Liste A entnommen wurde.

Überschreitet diese Zählvariable einen zuvor festgelegten Grenzwert, wertet Tim Sort dies als ein Indiz dafür, dass sich der Aufwand den “Galloping” Modus zu verwenden lohnen könnte und wechselt in eben diesen. Der Name “Galopping” zu deutsch Galoppieren, darf durchaus als Analogie zum Galoppieren von Pferden verstanden werden. Analog zu einem Pferd für welches der Galopp eine Symbiose zwischen Springen und schnellem Laufen ist, galloppiert Tim Sort über den zu durchsuchenden Bereich. Es soll bestimmt werden, in welchem Bereich der Block endet. Anschließend wird mit einer binären Suche über den zuvor fest gelegten Ziel-Bereich das exakte Ende des Blockes bestimmt. Die Suche am Anfang der Liste führt aus empirischen Überlegungen betreffend der Datensbeschaffentheit schneller zum Erfolg, als wenn sie in der Mitte der Menge begonnen würde. Wird der “Galopping״ Modus beendet, weil im aktuell bearbeiteten Bereich keine Blö­cke gefunden wurden, wird der Schwellenwert ihn zu erreichen um 1 erhöht. Je länger er allerdings ausgeführt wird, desto niedriger wird der Schwellenwert. Auf diese Weise versucht Tim Sort sicherzustellen, dass die Kosten dieses Verfall- resn gebeniiber dem Nutzen in einem vertretbaren Verhältnis stehen. Hierbei gilt, dass die Wahrscheinlichkeit zu Galoppieren mit der Anzahl der erfolgrei­chen Durchführungen steigt und analog dazu sinkt wenn die Erfolge ausbleiben. In [McIlroy(I993)] wird ein Algorithmus namens MSES (Merge Sort with Ex­ponential Search) vorgestellt, der nahezu identisch wie der Galopping Teil von Tim Sort arbeitet inklusive mathematischer Überlegungen hierzu.

Es bleibt die Frage offen, wann es zu einer Verschmelzung kommt:

Sobald ein neues Arbeitspaket, in Form einer zu verschmelzenden Teilmenge markiert wurde, prüft Tim Sort, ob es an der Zeit ist ein oder mehrere Arbeitspa­kete zu verschmelzen. Tim Sort hat den Anspruch ein stabiler Sortieralgorithmus zu sein, somit dürfen nur benachbarte Arbeitspakete miteinander verschmolzen werden. Sonst käme es zu einem Vertauschen der Reihenfolge gleicher Elemente relativ zueinander. Wenn drei Arbeitspakete А, в und c vorliegen, können entwe­der A und в oder в und c verschmolzen werden und anschließend beispielsweise AB und c. Wir rufen uns die Invarianten aufgrund des vorangegangenen Tei­lungsprozess in Erinnerung: Alle Arbeitspakete haben eine Mindestlänge, können aber beliebig lang sein. Die Entscheidung welche Pakete zu welchem Zeitpunkt verschmolzen werden versucht einen Kompromiss zwischen folgenden Aspekten zu finden:

Ein Arbeitspaket zu markieren kostet den Algorithmus zusätzlichen Speicher gegenüber den Eingabedaten, deshalb soll hiervon möglichst wenig Gebrauch gemacht werden.

Man möchte die zu verschmelzenden Listen möglichst gleich groß halten, da dies in den meisten Fällen effektiver ist. Wie bereits erläutert werden für das verschmelzen zweier Listen A und в mit dem “One pair at a time” Verfahren genau (A+B)-l Vergleiche benötigt. Wenn wir zwei Listen mit jeweils 5 Elemen­ten verschmelzen benötigen wir 9 Vergleiche. Bei einer Liste mit einem Element und 9 Elementen sind es ebenfalls 9 Vergleiche. Zwei unabhängige Listen zu ver­schmelzen ist ebenso aufwändig wie ein Element korrekt einzusortieren, wobei Ersteres einen größeren Nutzen bietet.

Die obere Schranke dieses Algorithmus wird vom Autor wie folgt angegeben: 0(11 log n) [Peters(2002)]

Bedauerlicherweise wird hierzu kein mathematischer Beweis aufgeführt. Das in dieser Arbeit gemessene Performanceverhalten des Algorithmus deutet allerdings ebenfalls auf diese obere Schranke hin.

Weitere Informationen finden sich in einem von Tim Peters verfassten Textdoku­ment [Peters (2002)], in dem er den Algorithmus und seine Designentscheidungen erläutert. Dieser Abschnitt über die Funktionsweise von Tim Sort basiert auf die- sem Textdokument sowie der Analyse der Java Implementierung von Josh Bloch im Rahmen des JDK 7.[Bloch(2009)]

Implementierung von TimSort Der Übersicht halber folgt zunächst eine Liste der implementierten Funktionen und eine Beschreibung ihrer Aufgaben. Anschließend folgt ein Diagramm welches darstellt, welche Funktionen dahin­gehend mit anderen Funktionen in Beziehung stehen, dass diese sie aufrufen. Zuletzt folgt eine abgewandelte Pseudocodeimplementierung, welche die wesent- liehen Merkmale erläutern soll. Eine vollständige Python Implementierung be­findet sich im Anhang B.

sort Die Hauptfunktion des SortierAlgorithmus. Es wird anhand eines Grenz­wertes entschieden ob die Eingabemenge von der Länge her den Overhead eines kompletten Merge Verfahrens rechtfertigt oder ob ein binärer Inserti­onsort ausreicht. Weiherhin werden hier in einer Hauptschleife die Arbeits­pakete geschnürt und das Verschmelzen angestoßen, bis alle Eingabedaten bearbeitet worden sind.

array Copy Inspiriert von der Java Funktion System, array copy, kopiert diese Funktion einen definierten Bereich von Elementen einer Quellliste an die gewünschte Position in einer Zielliste binary Sort Ein binärer Insertionsort, der zum Sortieren von kleinen Datensät­zen verwendet wird. countRunAndMakeAscending Diese Funktion sucht in einem vorgegebenen Bereich aufsteigende oder absteigende Reihen, wobei letztere mit Hilfe der Funktion reverseRange in eine aufsteigende Reihe umgewandelt werden. reverseRange erhält eine Eingabeliste und kehrt deren Reihenfolge um minRunLength Funktion zur Berechnung der minimalen Länge eines Arbeit­spaketes pushRun Funktion zum Markieren von Arbeitspaketen mergeCollapse Stößt unter gewissen Vorraussetzungen eine Verschmelzung von Arbeitspaketen an mergeForceCollapse Stößt, eine Verschmelzung von Arbeitspaketen an, ohne Vorraussetzungen dafür zu prüfen. mergeAt Funktion um die Verschmelzung zweier Bereiche zu starten mergeLo / mergeHi verschmelzt zwei Bereiche der Eingabedaten.mergeLo falls der vorherige Bereich kleiner oder gleich dem nachfolgendem Bereich ist, an­sonsten mergeHi gallopLeft / gallopRight Identifizierung von Blöcken: In einer Variante, bei der eine Liste von links nach rechts durchsucht wird: gallopLeft und in einer Variante in der eine Liste von rechts nach links durchsucht wird: gallopRight.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3 Die Beziehungen der Funktionen zueinander

Abbildung in dieser Leseprobe nicht enthalten

Listing 1.5. Tim Sort Pseudocode

Zwischenfazit Aus der Länge der Beispielimplementierung als auch den dazu nötigen Erklärungen bezüglich der Funktionsweise von Tim Sort lässt sich leicht erkennen, dass es sich hierbei um einen eher komplexen Algorithmus handelt. Die Grundidee eines Mergesort Algorithmus, das Problem in Teilprobleme zu zerle­gen und diese für sich zu lösen, wird in Tim Sort nach wie vor verfolgt. Allerdings liegt das Hauptaugenmerk des Algorithmus darauf Optimierungsmöglichkeiten bei Eingabedaten, die nicht vollständig und gleichverteilt zufällig sind, zu nut­zen.

“It’s generally true in this algorithm that we’re willing to gamble a little to win a lot” [Peters (2002)]

Dieses Zitat, von Tim Peters beschreibt viele Designentscheidungen. Das Ziel war es größtmöglichen Nutzen aus der Beschaffenheit von Spezialfällen zu ziehen, oh­ne dabei zu viel Leistung bei anderen Fällen einbüßen zu müssen.

4 Performancemessungen

Nachdem die Algorithmen theoretisch untersucht worden sind, wurden im Rah­men dieser Arbeit auch experimentelle Tests durchgeführt, um die Sortierge­schwindigkeit der Algorithmen auf Testdaten zu untersuchen und miteinander zu vergleichen.

4.1 Durchführung der Tests

Die Testdaten bestehen aus einer zufällig angeordneten Mengen von Zahlen zwi- sehen 0 und einem Maximalwert+1000. Von 10 beginnend wurde der Maximal­wert schrittweise um eine Zehnerpotenz erhöht bis hin zu 100.000.000 Elemen­ten. Hierbei wurde in jedem Schritt auch eine Testreihe mit ungeraden Zahlen erzeugt, um zu ermitteln ob sich die zu testenten Algorithmen bei ungeraden Eingabemengen anders verhalten. Im Bereich von 10 bis 10.000.001 Elemen­ten wurden pro Testreihe 15 Testdatensätze erzeugt im Bereich von 100.000.000 Elementen waren es 10 Testdatensätze. Alle Tests wurden auf einer Workstati­on des IT-Service Zentrums der Universität Kassel durchgeführt. Per Software wurde jeder Algorithmus auf 6 GB Speicherverbrauch und 72 Stunden maximale CPU Zeit begrenzt. Wie in der Tabelle 2 ersichtlich, können für den Enhanced- Bubblesort-Algorithmus im Bereich ab 1.000.001 Elementen keine Messerbeg- nisse vorgelegt werden, da dieser die CPU Zeitbegrenzung überschritten hat. Um eine Referenz zu haben, auf die man sich in den Tests beziehen kann wurde neben den Testkandidaten, die pythoninterne Sortierfunktion von Listen verwen­det. Es handelt sich hierbei um einen in c implementierten Timsort Algorithmus [Peters(2002)] Für jeden Algorithmus wurde die benötigte Zeit zur Sortierung in CPU Sekunden - welche von einem Pyhton Modul namens cProfile gemessen wurde - durch die entsprechende Zeit der Referenzsortierung geteilt, so fern die Referenzsortierung mehr als 0,001 CPU Sekunden benötigte.

Als weitere Referenz für die Messungen wurde ein Quicksortalgorithmus eingesetzt.

Abbildung in dieser Leseprobe nicht enthalten

Quelle [LiterateProgrammsWiki(2009)]

Listing 1.6. Quicksort

4.2 Testergebnisse

Die Tabellen 1 und 2 bilden die Grundlage der Diagramme: die Spalte “rela­tiv” bezieht, sich auf den links befindlichen Algorithmus und stellt die relative Laufzeit dar. Enthält die Spalte keinen Wert bedeutet dies, dass die Referenz­Sortierung weniger als den Mindestwert von 0,001 CPU Sekunden benötigt hat, so dass eine Referenzbildung zu einer Teilung durch Null geführt hätte. Weiter­hin lassen sich die durchschnittlich gemessenen absoluten Sortierzeiten für jeden getesteten Algorithmus in der entsprechend benannten Spalte ablesen.

Abbildung 3 visualisiert die absolute Laufzeit in CPU Sekunden, die ein Sor­tieralgorithmus für die korrekte Sortierung benötigt hat. Alle Algorithmen ha­ben im Bereich kleiner 1000 Elemente weniger als die Minimalschwelle von 0,001 CPU Sekunden benötigt, was im Diagramm ersichtlich ist.

Die Abbildung 4 visualisiert die relativen Laufzeiten der Algorithmen zueinan­der. Die relativen Laufzeiten stellen den Quotienten aus der absoluten Laufzeit des Algorithmus und der absoluten Laufzeit der Referenzsortierung dar.

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3. Laufzeiten der verschiedenen Sortieralgorithmen

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 4. Die verschiedenen Sortieralgorithmen relativ zur Referenzmessung

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1. Messergebnisse Teil 1 - Einheit für die Messung: CPU Sekunden

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2. Messergebnisse Teil 2 - Einheit für die Messung: CPU Sekunden

4.3 Auswertung

Aus Abbildung 3 (4.2() lässt sich ein Gesamtüberblick ableiten. Es existieren im Wesentlichen drei Abstufungen: Enhanced-Bubblesort zeigte mit Abstand die geringste Performance, nahezu linear abhängig von der Eingabedatenmen­ge. Die beiden Shellsortvarianten befinden sich im Mittelfeld und Timsort sowie Quicksort zeigten sich als schnellste Algorithmen im Test.

Beachtrachtenswert ist zunächst das Verhältnis von Shell Sort zu Enhanced Shell Sort, welches sich in Abbildung 4 (4.2) nachvollziehen lässt: Während Shell Sort bei den Testreihen bis einschließlich einer Millionen Datensätze erkennbar im Geschwindigkeitsvorteil ist, kehrt sich dieser Effekt bei größeren Datenmengen um, wenn auch der Geschwindigkeitsvorsprung von Enhanced Shell Sort verhält­nismäßig geringer ausfällt.

Bemerkenswert ist weiterhin, dass Shell Sort im Bereich von zehntausend Eie- menten deutlicher Testsieger ist (siehe hierzu auch Tabelle f) und auch die bei­den Favoriten Quicksort und Tim Sort (Tabelle 2) hinter sich lässt. An dieser Stelle könnten sich die vielen Funktionsaufrufe - die unter Python messbar ver­zögernd sind - signifikant negativ ausgewirkt haben. Shell Sort hingegen kommt mit deutlich weniger Funktionsaufrufen und auch Fallunterscheidungen zurecht.

Gesamtsieger des Vergleiches ist Tim Sort welcher nur in den Kategorien Zehn­tausend Datensätze und Zehnmillionen Datensätze nicht am schnellsten sortier­te. Hierbei sei betont, dass die erzeugten Daten einige Duplikate enthalten, sowie durch die randomisierte Erzeugung kaum Struktur aufweisen. Somit sollte Tim Sort den Vorteil der Optimierungen nicht signifikant genutzt haben können, da diese darauf ausgerichtet sind bestehende Teilsortierungen der Eingabemenge zu nutzen, die in den Testdaten kaum zu finden waren. Quicksort war meist lang­samer als Timsort allerdings nicht deutlich wie sich besonders in Abbildung 4.2 aber auch in den Tabellen ab lesen lässt.

5 Fazit / Ausblick

Diese Arbeit hat sich mit dem Problem der Sortierung von Datensätzen be­schäftigt und dieses an drei sehr unterschiedlichen Algorithmen examplarisch weiter ausgeführt, indem verschiedene Herangehensweisen erläutert, analysiert und miteinander verglichen wurden. Betonen wir zunächst die Gemeinsamkei­ten: Diese besteht bei den untersuchten Algorithmen darin, dass bei allen drei Algorithmen auch noch in den letzten Jahren Bemühungen erfolgt sind, diese weiter zu entwickeln. Und dies obwohl die Algorithmen in ihrer Grundidee be­reits seit mehreren Jahrzehnten bekannt sind.

Der betrachtete Enhanced Bubble Sort Algorithmus hat große Erwartungen ge­weckt. Diese wurden allerdings nicht erfüllt. Es zeigt sich an der Publikation wel- eher der Algorithmus zu Grunde liegt [Alnihoud und Mansi(20f0)], dass es für die Qualität einer wissenschaftlichen Arbeit von großer Bedeutung ist, Quellen und deren Aussagen zu prüfen, auch wenn diese bei oberflächlicher Betrachung schlüssig erscheinen.

Enhanced Shell Sort zeigt, dass die Optimierung eines Algorithmus nicht Zwangs­läufig mit drastischen Verfahrensänderungen zu tun haben muss, sondern dass auch einzelne Variablen eine große Bedeutung haben können. Wie auch Robert Sedgewick in [Sedgewick(2002)] komme ich ebenfalls zu dem Schluss, dass Shell­sort in der Praxis die erste Wahl ist, wenn eine einfache Implementierung bei annehmbarer Performance gefordert ist.

Tim Sort, der zukünftige Standardalgorithmus zum Sortieren von Arrays in der Programmiersprache Java, der sich seit Version 2.3 in Python bewährt hat, be­nötigt mit Abstand den längsten Quelltext. Die vielen Facetten zu erläutern hat einen großen Teil dieser Arbeit in Anspruch genommen. Dennoch ist es beachtenswert, wie sich einzelne Überlegungen und Optimierungen so zu einem Gesamtalgorithmus zusammenfügen ließen. Anhand von Tim Sort kann man viel über das Sortieren lernen und auch das Zusammenführen zweier Datenmengen - welches auch in anderen Bereichen der Informatik Anwendung findet - wird pra­xisnah, intensiv und dennoch mit einem vorhandenem theoretischem Unterbau behandelt.

In dieser Arbeit wird auch klar, dass in der secļuenziellen Sortierung in den letzten Jahren keine Quantensprünge stattgefunden haben und auch nicht zu er­warten sind. Dennoch handelt es sich beim Sortieren weiterhin um ein wichtiges und aktuelles Problem. Allerdings liegt die Zukunft klar in dem Entwickeln pas­sender Algorithmen für aktuelle Mehrprozessorsysteme bis hin zu Clustersyste­men. Nicht umsonst findet jährlich ein Wettbewerb statt, bei dem Universitäten aber auch industrielle Forschungseinrichtungen darum konkurrieren, eine mög- liehst, performante aber auch eine resourcenschonende Sortierung zu erreichen, die auch mit Datenmengen umgehen kann, die in keinen derzeit verfügbaren Hauptspeicher passen (Siehe hierzu http://sortbenchmark.org/)

Neben der umfangreichen Dokumentation des Autors Tim Peters und einzel­nen Blog Beiträgen existieren meines Wissens leider keinerlei Veröffentlichungen und Analysen zum Tim Sort Algorithmus. Möglicherweise wäre es lohnenswert zu untersuchen, in wie weit sich dieser Algorithmus bzw. dessen Konzepte auf eine parallisierte Umgebung anpassen lassen und wie sich dieser Algorithmus im Vergleich zu anderen platzieren würde.

6 Danksagung

Ich danke Robert Jäschke für die Auswahl des Seminarthemas sowie Gerd Stum­me für die Betreuung. Weiterhin möchte ich auf das Publikationsmanagement­system Bibsonomy ( http ://www.bibsonomy. org ) hinweisen, welches mir die Quellenorganisation deutlich erleichtert hat. Meine Quellen für verschiedene Ar­beiten sowie nützliche Links sind dort unter http : //www. bibsonomy. org/user/ kw zu finden.

Literatur

Alnihoud und Mansi(2010). Alnihoud und Mansi 2010 Alnihoud, Jehad ; Man­SI, Rami: An Enhancement of Major Sorting Algorithms. In: International

Arab Journal of Information Technology (IAJIT) 7 (2010), Nr. 1, s. 55 - 62.

- URL http ://search.ebscohost.com/login.aspx?direct=true&db=iih&AN= 48633561&site=ehost-live. - ISSN 16833198

Bender u. a.(2006)Bender, Farach-Colton und Mosteiro. Bender и. a. 2006 Bender, Michael ; Farach-Colton, Martin ; Mosteiro, Miguel: Insertion Sort is 0(11 log n). In: Theory of Computing System:s 39 (2006), Nr. 3, s. 391 - 397.

- URL http ://search.ebscohost.com/login.aspx?direct=true&db=iih&AN= 20700425&site=ehost-live. - ISSN 14324350

Bloch(2009). Bloch 2009 Bloch, Josh ; Inc., Google (Hrsg.): Tim,Sort.java. Ja­va Quelltext. 2009. - URL http://hg.openjdk.java.net/jdk7/tl/jdk/file/ bfd7abda8f79\/srс/share/classes/java/util/TimSort.java. - Zugriffsdatum: 20.06.2010

LiterateProgrammsWiki(2009). LiterateProgrammsWiki 2009 Literate- ProgrammsWiki: Quicksort (Python). (2009). - URL http:

//en.literateprograms.org/Quicksort_(Python). - Zugriffsdatum: 20.06.2010 McIlroy(1993). Mcllroy 1993 McIlroy, Peter: Optimistic sorting and information theoretic complexity. In: SODA ’93: Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms. Philadelphia, PA, USA : Society for Industrial and Applied Mathematics, 1993, s. 467-474. - ISBN 0-89871-313-7 jjb (Nickname)(2009). jjb (Nickname) 2009 (Nickname) jjb ; (openjdk.java.net), Oracle Corporation / Openjdk c. (Hrsg.): 6804124: Replace "modified mergesortïn java.util.Arrays.sort with timsort. Quellcodeänderung. 2009. - URL http://hg. 0penjdk.java.net/jdk7/tl/jdk/rev/bfd7abda8f79. - Zugriffsdatum: 20.06.2010 Peters(2002). Peters 2002 Peters, Tim ; (Python.org), Python Software F. (Hrsg.): Distsort / Timsort. 2002. - URL http://svn.python.org/view/python/ trunk/Objects/listsort. txt?revision=69846. - Zugriffsdatum: 08.07.2010 Sedgewick(2002). Sedgewick 2002 Sedgewick, Robert ; Studium, Pearson (Hrsg.): Algorithmen in c++ Teil 1-4 Dritte. Martin-Kollar-Str. 10-12. 81829 München : Pearson Studium, 2002

Shahzad und Afzal(2007). Shahzad und Afzal 2007 Shahzad, Basit ; Afzal, Mu­hammad T.: Enhanced Shell Sorting Algorithm. In: Enformatika 21 (2007), s. 66 - 70. - URL http ://search.ebscohost.com/login.aspx?direct=true&db= iih&AN=27981807&site=ehost-live. - ISSN 1.3055313 Shell(1959). Shell 1959 Shell, Donald L.: A High-Speed Sorting Procedure. In: Commun. ACM 2 (1959), Nr. 7, s. 30-32. - URL http://dblp.uni-trier.de/ db/j ournals/cacm/cacm2.html#Shell59

Teschi und Teschi(2008). Teschi und Teschi 2008 Teschl, Gerald ; Teschl, Susan­ne ; Berlin, Springer (Hrsg.): Mathematik für Informatiker. Bd. 1: Mathematik für Informatiker: Band 1: Diskrete Mathematik und Lineare Algebra. Zweite. Springer, Mai 2008

A Python-Scripte zum Durchführen der Performancetests import random import sys

Abbildung in dieser Leseprobe nicht enthalten

Listing 1.7. genvals.py - Script zum Erzeugen der Testdaten

Das Script erhält drei Eingabeparameter: Die maximale Anzahl der Elemente, die Anzahl der Durchgänge pro Stufe sowie den Namen der Ausgabedatei. In Zeile 7 wird eine Funktion nextrandom definiert, welche zu einem Eingabepara­meter X eine Zufallszahl zwischen 0 und 1000 addiert. In Zeile 13 wird zunächst eine Liste zwischen 0 und der gewünschten Anzahl von Listenelementen erzeugt. Mittels der map Funktion wird die nextrandom Funktion auf jeden Element der Liste aufgerufen. Anschließend wird die Liste in Zeile 14 zufällig umgeordnet. Dies geschieht für jede Zehnerpotenzstufe, jeweils für eine gerade als auch für eine ungerade Liste jeweils pro Duchgang. Die Ausgabedateinamen haben das folgende Format:

VomNutzerDefinierterDateiname_AnzahlDerElemente_AktuellerDurchlauf

Desweiteren wurden zwei Funktionen definiert, welche die Tests unterstützt ha­ben:

“readfile” liest die bereits definierten Testdatensätze in den Speicher ein, um sie den Algorithmen zur Verfügung zu stellen.

“checkdata״ stellt die Korrektheit der Sortierung sicher, um ggf. Fehler aufzude­cken.

Abbildung in dieser Leseprobe nicht enthalten

Listing 1.8. testframework.py - Hilfsfunktionen für den Test Es folgt die einheitlich genutze Funktion zum Testen eines Algorithmus:

Abbildung in dieser Leseprobe nicht enthalten

Listing 1.9. Testfunktion

Wie in Zeile 17 ersichtlich wird die Funktion “dotest״ nicht direkt aufgerufen, sondern indirekt über cProfile. Hierbei handelt es sich um eine an Python ange­bundene C-Bibliotek, die für die Performancemessungen verwendet wurde.

B Vollständige Python-Implementierung von Timsort

Abbildung in dieser Leseprobe nicht enthalten

Listing 1.10. TimSort