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.
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.
Auf einen Blick
- Note: 1,0
- Praktische Vergleiche von binärer und linearer Suche sowie Quicksort und BubbleSort
- Abgebildeter R-Quellcode für die binäre Suche
- Abgebildete R-Implementierung von Quicksort nach einer Vorlage von GitHub Gist
- 10 Quellen im Literaturverzeichnis
Inhaltsverzeichnis
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
Zielsetzung und Themen
Die Arbeit untersucht, wie sich die Laufzeit der binären Suche und von Quicksort im Vergleich zu anderen Such- und Sortieralgorithmen beschreiben lässt. Dazu erläutert sie deren Funktionsweise und Implementierung in R und betrachtet ihre Komplexitätsklassen anhand praktischer Beispiele.
- Definition und Eigenschaften von Algorithmen
- Funktionsweise und Implementierung der binären Suche
- Funktionsweise, Effizienz und Implementierung von Quicksort
- Vergleich mit linearer Suche und BubbleSort
- Laufzeitkomplexität und Grenzen des Vergleichs
Auszug aus dem Buch
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.
Zusammenfassung der Kapitel
1. Einleitung: Die Einleitung begründet die Bedeutung von Such- und Sortieralgorithmen und formuliert das Ziel des Laufzeitvergleichs.
2. Grundlagen: Das Kapitel definiert den Begriff Algorithmus und stellt wesentliche Eigenschaften von Algorithmen vor.
3. Binäre Suche: Das Kapitel erläutert das Suchverfahren und beschreibt eine Implementierung in R.
4. Quicksort: Die Funktionsweise und Effizienz des Sortieralgorithmus werden erklärt und eine Implementierung in R vorgestellt.
5. Laufzeitvergleich mit anderen Algorithmen: Anhand konkreter Eingaben werden binäre und lineare Suche sowie Quicksort und BubbleSort miteinander verglichen.
6. Kritische Betrachtung: Der Autor grenzt den Vergleich ein und weist darauf hin, dass weder Speicherbedarf noch tatsächliche Zeitmessungen untersucht werden.
7. Fazit: Das Fazit fasst Vorgehen und Vergleich zusammen und nennt weitere Einflussfaktoren auf die Effizienz.
8. Ausblick: Der Ausblick stellt Fragen zu hybriden Sortierverfahren und zur Verbesserung von Implementierungen.
Schlüsselwörter
Algorithmen, binäre Suche, lineare Suche, Quicksort, BubbleSort, Laufzeitvergleich, Laufzeitkomplexität, Landau-Notation, Sortierverfahren, Suchverfahren, Programmiersprache R, Teile und herrsche
Häufig gestellte Fragen
Worum geht es in der Arbeit?
Die Arbeit behandelt Such- und Sortieralgorithmen und vergleicht die Laufzeit der binären Suche und von Quicksort mit jeweils einem anderen Verfahren.
Welche Themenfelder stehen im Mittelpunkt?
Im Mittelpunkt stehen Algorithmeneigenschaften, Funktionsweisen, Implementierungen in R und die Analyse der Laufzeitkomplexität.
Was ist das Ziel der Untersuchung?
Der Autor möchte die Laufzeit der binären Suche und von Quicksort mit anderen Algorithmen ihrer Art vergleichen und ihre Komplexitätsklassen bestimmen.
Welche wissenschaftliche Methode wird verwendet?
Die Arbeit erläutert die Verfahren anhand von Fachliteratur und vergleicht sie an praktischen Beispielen. Dabei betrachtet sie die Anzahl der Schritte beziehungsweise Vergleiche und verwendet die Landau-Notation.
Was behandelt der Hauptteil?
Der Hauptteil erklärt die binäre Suche und Quicksort, beschreibt Implementierungen in R und vergleicht beide Verfahren mit Alternativen.
Welche Schlüsselwörter charakterisieren die Arbeit?
Wichtige Begriffe sind binäre Suche, Quicksort, lineare Suche, BubbleSort, Laufzeitkomplexität, Landau-Notation und R.
Welche Algorithmen werden unmittelbar miteinander verglichen?
Die binäre Suche wird mit der linearen Suche verglichen; Quicksort wird BubbleSort gegenübergestellt.
Welches Material zur Programmierung enthält die Arbeit?
Sie zeigt Quellcode zur binären Suche und zu Quicksort in R als Abbildungen und erläutert die jeweiligen Implementierungen.
Welche Grenzen nennt der Autor für seinen Vergleich?
Der Vergleich betrachtet keine gemessenen Zeiten und berücksichtigt weder eine Speicheranalyse noch die Effizienz des Quellcodes. Außerdem werden nur ausgewählte Vergleichsalgorithmen behandelt.
- Citar trabajo
- Octavian Zaiat (Autor), 2020, Laufzeitvergleich von Such- und Sortieralgorithmen am Beispiel der Binären Suche und Quicksort, Múnich, GRIN Verlag, https://www.grin.com/document/958073