Laufzeitvergleich von Such- und Sortieralgorithmen am Beispiel der Binären Suche und Quicksort

Inhaltsverzeichnis

Abbildungsverzeichnis

1. Einleitung

2. Grundlagen
2.1 Definition des Algorithmus
2.2 Eigenschaften

3. Binäre Suche
3.1 Funktionsweise
3.2 Implementierung in R

4. Quicksort
4.1 Funktionsweise
4.2 Effizienz des Quicksort
4.3 Implementierung in R

5. Laufzeitvergleich mit anderen Algorithmen
5.1 Vergleich des Algorithmus - Binäre Suche
5.2 Vergleich des Algorithmus - Quicksort

6. Kritische Betrachtung

7. Fazit

8. Ausblick

9. Literaturverzeichnis

Abbildungsverzeichnis

Abbildung 1: Binäre Suche in R 4

Abbildung 2: Quicksort in R 6

1. Einleitung

Aufgaben wie das Suchen und Sortieren von Daten sind in fast jeder Anwendung zu finden. Für das Lösen dieser Aufgaben stehen verschiedene Algorithmen zur Verfügung, die sich in ihrer Komplexität unterscheiden. Einen Laufzeitvergleich der Algorithmen gibt einen Hinweis darüber, für welchen Anwendungsfall am besten geeignet sie sind. Eine Laufzeitanalyse hilft den besten Algorithmus für die bevorstehende Problemstellung zu wählen. Somit wird unnötig Speicherplatz verbraucht und die Anwendung führt ihre Aufgabe effizient aus.¹ Das Sortieren der Daten ist eine der wichtigsten Aufgaben der Algorithmen, deshalb gibt es auch zahlreiche Methoden, die ihre Stärken und Schwächen haben und dabei die Effizienz des Algorithmus beeinflussen.²

Es soll in dieser Arbeit die Laufzeit des Suchalgorithmus (Binäre Suche) und des Sortieralgorithmus (QuickSort) mit anderen Algorithmen ihrer Art verglichen und ihre Komplexitätsklassen festgestellt werden.

2. Grundlagen

Für den Einstieg in das Thema ist es notwendig die Definition des Algorithmus und seine Eigenschaften zu betrachten.

2.1 Definition des Algorithmus

Definition: „Ein Algorithmus (algorithm) ist eine vollständige, präzise und in einer Notation oder Sprache mit exakter Definition abgefasste, endliche Beschreibung eines schrittweisen Problemlösungsverfahrens zur Ermittlung gesuchter Datenobjekte (ihrer Werte) aus gegebenen Werten von Datenobjekten, in dem jeder Schritt aus einer Anzahl ausführbarer, eindeutiger Aktionen und einer Angabe über den nächsten Schritt besteht.“³

2.2 Eigenschaften

Ein Algorithmus besitzt folgende Eigenschaften:

- Determinismus - Nach jeder Ausführung muss der nächste Schritt eindeutig sein,
- Endlichkeit - Der Algorithmus ist endlich, wenn er nach einer endlichen Anzahl von Schritten zu einem Ergebnis kommt.⁴
- Ausführbarkeit - Jeder Schritt muss ausführbar sein.⁵
- Parametrisierbarkeit - Der Algorithmus soll eine Klasse von Problemen lösen können,
- Finitheit - Der Algorithmus hat eine endliche Länge,
- Determiniertheit - Der Algorithmus liefert unter gleichen Bedingungen das gleiche Ergebnis,
- Terminierung - Der Algorithmus muss nach endlichen ausgeführten Schritten terminieren und ein Ergebnis liefern,
- Eindeutigkeit - Für die Lösung eines Problems liefert der Algorithmus nur eine eindeutige Beschreibung.⁶

3. Binäre Suche

In diesem Kapitel wird die Funktionsweise des Suchalgorithmus „Binäre Suche“ erläutert und wie der Algorithmus in R implementiert wird.

3.1 Funktionsweise

Der Algorithmus setzt voraus, dass die Elemente in einem Array sortiert sind, andernfalls funktioniert er nicht richtig. Die Binäre Suche gehört zu der Gruppe von Algorithmen, die das „teile und herrsche“-Prinzip verwendet. Er spaltet das Array in zwei Bereiche auf, nachdem das Pivot-Element (Median) gefunden wurde. Das gesuchte Element wird mit dem Pivot-Element verglichen. Die Suche wird beendet, wenn das gesuchte Element dem Pivot-Element entspricht. Ist das Element kleiner als das Pivot-Element, befindet sich das Element links von Pivot. Ist das gesuchte Element größer als das Pivot, befindet sich das gesuchte Element rechts von Pivot. Die resultierenden Bereiche sind immer halb so groß, wie der ursprüngliche Bereich.⁷ Die Laufzeitkomplexität ist bei der Binären Suche im „worst case“ O(log n) und im „best case“ O(1).⁸

3.2 Implementierung in R

Für die Implementierung des Algorithmus-Binäre Suche habe ich mich für R entschieden. In der ersten Zeile des Quellcodes wird die Funktion BinaereSuche initialisiert. Diese Funktion beinhaltet zwei Parameter, die ich mit Daten und Suchwert benannt habe. Es wird eine Funktion length() benötigt, die die Länge des Arrays bestimmen kann. Dieser Funktion wird als Parameter Daten übergeben und in der Variable rechts gespeichert. In der Variable links wird der Wert 1 als Anfangswert zugewiesen. Die while -Schleife wird benötigt, um das Array komplett von Anfang bis Ende durchlaufen zu können. Solange die Variable links kleiner als die Variable rechts ist, wird die Schleife durchlaufen. Befindet sich der gesuchte Wert nicht in der Liste, dann wird mittels Keyword return ein String ausgegeben („Der gesuchte Wert befindet sich nicht in der Liste“). Innerhalb der while -Schleife werden folgende Anweisungen formuliert:

- Es wird eine Variable benötigt, die das Pivot-Element festlegen muss. In der Variable Pivot wird der Median ausgerechnet und gespeichert.
- Eine if -Bedingung prüft, ob das Pivot-Element gleich dem gesuchten Wert ist. Ist die Bedingung erfüllt, wird mit return ein String ausgegeben und die Schleife beendet.
- Eine andere if -Bedingung prüft, ob das Pivot-Element größer als der gesuchte Wert ist. Ist die Bedingung wahr, wird das Pivot um 1 dekrementiert und in der Variable rechts gespeichert.
- Die letzte if -Bedingung prüft, ob das Pivot kleiner als der Suchwert ist. Ist die Bedingung erfüllt, wird die Variable links um 1 inkrementiert und in der selben Variable gespeichert.

Die Abbildung 1 zeigt eine mögliche Lösung für die Implementierung der Binären Suche in R.

Abbildung 1 : Binäre Suche in R

Abbildung in dieser Leseprobe nicht enthalten

Quelle: Eigene Darstellung

4. Quicksort

In diesem Kapitel beschäftige ich mich mit dem Sortieralgorithmus „Quicksort“. Es soll hierbei die Funktionsweise und dessen Effizienz erläutert und die Implementierung in R demonstriert werden.

4.1 Funktionsweise

Quicksort ist ein Algorithmus, der zum Sortieren großer Datenmengen eingesetzt wird. Der Algorithmus wählt aus einer Reihenfolge von Daten ein Element, im besten Fall der Median, der auch als Pivot-Element bezeichnet wird, und teilt die gesamte Datenmenge in zwei Bereiche auf. Die restlichen Elemente werden entsprechend dem Pivot-Element sortiert. Alle Elemente, die kleiner oder gleich dem Pivot-Element sind, werden im linken Bereich verschoben und alle die größer als das Pivot-Element sind, werden in rechten Bereich verschoben. Innerhalb dieser Bereiche wählt der Algorithmus ein neues Pivot-Element und spaltet die Elemente weiter. Die Sortierung wird beendet, wenn der selektierte Bereich nur ein einziges Element enthält.⁹

Die Laufzeitkomplexität wird mit der O-Notation angegeben und ist bei Quicksort im „best case“ O(n*log(n)), wenn die aufgeteilten Bereiche immer gleich lang sind. Das „worst case“-Szenario tritt auf, wenn die aufgeteilten Bereiche nicht mehr gleich lang sind. In diesem Fall ist die Komplexität quadratisch O(n2).¹⁰

4.2 Effizienz des Quicksort

Um eine Aussage über die Effizienz des Quicksort zu treffen, muss das Verhältnis der Partitionen betrachtet werden. Bei der balancierten Partition verarbeitet der Algorithmus das Sortierverfahren schneller als bei unbalancierter Partition. Wie schon oben erläutert, ist im schlechtesten Fall das Verhalten des Algorithmus O(n2) und die Rekursionsgleichung lautet T(n)=T(n-1)+T(0)+O(n). Auch bei einer vollständigen geordneten Liste kann die Komplexität quadratisch sein. Ist die Partition balanciert, werden zwei Teilprobleme erzeugt. Diese teilen sich die Größen in [n/2] und [n/2]-1. Die Rekursionsgleichung sieht so aus: T(n)<2T(n/2)+O(n).¹¹

4.3 Implementierung in R

Für die Implementierung des Algorithmus habe ich mich für R entschieden. Es wird eine Funktion mit dem Namen quickSort () initialisiert. Dieser wird das Parameter Daten übergeben. Als Nächstes wird die Funktion sample() benötigt, um in R ein Random-Wert aus Daten zu selektieren. Der selektierte Wert wird der Variable pivot zugewiesen. Es werden noch die Arrays left und right benötigt, um zwei Teilbereiche links und rechts zwischen das Pivot-Element zu schaffen. Für die Verschiebung der Werte in linken und rechten Bereich wird die Funktion move() benötigt. Die if -Bedingung speichert alle Werte in left, die kleiner als das Pivot-Element sind. Alle anderen Werte werden mit else in der Variable right gespeichert. Die letzten if -Bedingungen sortieren die Werte jeweils im linken und rechten Bereich. Abschließend werden die sortierten Werte mit c(left, pivot, right) zurückgegeben.¹² Eine mögliche Lösung des Quicksort kann in der Abbildung 2 angesehen werden.

Abbildung 2 : Quicksort in R

Abbildung in dieser Leseprobe nicht enthalten

Quelle: In Anlehnung an https://gist.github.com/primaryobjects/c9020cf98168930eb019

5. Laufzeitvergleich mit anderen Algorithmen

Dieses Kapitel befasst sich mit dem Laufzeitvergleich des Quicksort und Binärer Suche. Die Algorithmen werden anhand eines praktischen Beispiels verglichen und am Ende Aussagen über ihre Effizienz getroffen. Die zentrale Frage bei der Komplexität der Algorithmen ist, wie schnell sie beim Sortieren oder Suchen sind.

Für die Berechnung der Laufzeitkomplexität wird die Landau-Notation verwendet. Um die Laufzeit der Algorithmen zu analysieren, wird die Größe der Eingabe benötigt, die meist auch als n bezeichnet wird.¹³

5.1 Vergleich des Algorithmus - Binäre Suche

In diesem Unterkapitel wird der Algorithmus Binäre Suche mit der Linearen Suche verglichen. Beide Algorithmen erhalten die gleichen Eingabewerte und sollen eine bestimmte Zahl suchen. Der Vergleich soll die Gesamtanzahl der Schritte anzeigen, die benötigt werden, bis die gesuchte Zahl gefunden wurde.

[...]

¹ Vgl. Knebl, H., Algorithmen und Datenstrukturen, 2019, S. 6.

² Vgl. Wegener, I., Effiziente Algorithmen für grundlegende Funktionen, 1991, S. 4.

³ Pomberger, G., Dobler, H., Algorithmen und Datenstrukturen, 2008, S. 33.

⁴ Vgl. Logofătu, D., Grundlegende Algorithmen mit Java, 2014, S. 10.

⁵ Vgl. Pomberger, G., Dobler, H., Algorithmen und Datenstrukturen, 2008, S. 34.

⁶ Vgl. Boles, D., Programmieren spielend gelernt mit dem Java-Hamster-Modell, 2013, S. 11.

⁷ Vgl. Knebl, H., Algorithmen und Datenstrukturen, 2019, S. 102.

⁸ Vgl. https://cg.informatik.uni-freiburg.de/course_notes/info2_10_suchen.pdf, Zugriff am 26.06.2020.

⁹ Vgl. Logofătu, D., Grundlegende Algorithmen mit Java, 2014, S. 148-149.

¹⁰ Vgl. ebd. S. 149.

¹¹ Vgl. Cormen, T. H. u. a., Algorithmen - eine Einführung, 2017, S. 175-176.

¹² Vgl. https://gist.github.com/primaryobjects/c9020cf98168930eb019, Zugriff am 26.06.2020.

¹³ Vgl. Kohn, W., Tamm, U., Mathematik für Wirtschaftsinformatiker, 2019, S. 171-172.