Alle Beiträge von Björn Karpenstein

Diplom Informatiker, Programmierer, Musikbegeisterter

Wie funktionieren Buffer Overflows und/oder Heap Overflows?

Intention

Vor einer aktuell kritischen Sicherheitslücke von älteren Microsoft Server Versionen, Windows 11 und Windows 10 wird in einem aktuellen Artikel auf heise.de gewarnt.

Diese offen gelegten Schwachstellen / Sicherheitslücken werden in einer öffentlichen Online-Datenbank aufgelistet:

Konkret handelt es sich dabei um die Ausnutzung von Heap-Overflows für das Einschleusen von Schadcode / schädlichem Code. In diesem Artikel möchte ich darauf eingehen, wie solche Heap-Overflows funktionieren, indem ich die Fragen beantworte, die sich mir vorher gestellt hatten.

Was ist der „Heap“, der überlaufen kann?

Zunächst ist eine Abgrenzung darüber nötig, was ein Heap eigentlich ist. In der Informatik gibt es zwei verschiedene Konzepte, die beide als „Heap“ bezeichnet werden:

  1. Heap im Speicher-Management: Dies bezieht sich auf den Bereich des Speichers, der für dynamische Speicherzuweisungen verwendet wird. Wenn Sie malloc() oder ähnliche Funktionen verwenden, wird der Speicher aus diesem Heap zugewiesen. Ein Heap Overflow tritt auf, wenn mehr Daten in einen Speicherbereich geschrieben werden, als dafür vorgesehen ist, was zu einer Beschädigung des Speichers führen kann.
  2. Heap als Datenstruktur: Wir haben in „Algorithmen und Datenstrukturen“ ebenfalls über Heaps gesprochen. Dies ist eine spezielle Baumstruktur, die bestimmte Eigenschaften erfüllt. Zum Beispiel ist ein Max-Heap ein binärer Baum, bei dem jeder Elternknoten größer oder gleich seinen Kindknoten ist. Diese Art von Heap wird häufig in Algorithmen wie Heapsort oder für Prioritätswarteschlangen verwendet.

Im Nachfolgenden beziehen wir uns auf Definition 1, da der Heap im dynamisch anforderbaren Speicherbereich liegt. Der Prozess kann also von diesem Bereich neuen Speicher für sich anfordern. Der Heap des Prozessspeichers beschränkt sich bei modernen Betriebssystemen auf den ausgeführten Prozess, was bedeutet dass ein Prozess nicht auf den Prozessspeichers eines anderen Prozesses zugreifen kann. Bei früheren Betriebssystemen wie beispielsweise MS DOS war dies noch nicht der Fall, da man hier z.B. direkt in den Bildwiederholspeicher Pixel in einer Farbe durch Speichermanipulation setzen konnte.

Ist die in Definition 1 genannte Beschädigung physisch?

Nein, die Beschädigung bei einem Heap Overflow ist nicht physisch. Sie betrifft den Speicherbereich des Computers und führt zu einer logischen Beschädigung der Daten. Das bedeutet, dass die Daten im Speicher durcheinandergebracht oder überschrieben werden, was zu Programmabstürzen, unerwartetem Verhalten oder Sicherheitslücken führen kann. Physische Hardware wird dabei nicht beschädigt.

Gibt es ein Beispiel, wie ein Heap Overflow zu einer Sicherheitslücke führen kann?

Stellen wir uns vor, ein Programm verwendet die Funktion malloc(), um Speicher für Benutzereingaben zu reservieren, überprüft jedoch nicht, ob die Eingabe die Größe des zugewiesenen Speichers überschreitet. Ein Angreifer könnte dann eine übermäßig große Eingabe senden, die mehr Speicherplatz benötigt, als zugewiesen wurde. Dies führt dazu, dass benachbarte Speicherbereiche überschrieben werden.

Ein konkretes Beispiel ist der Heap Overflow Angriff auf den Microsoft Internet Explorer im Jahr 2014. Angreifer nutzten eine Schwachstelle aus, bei der sie durch gezielte Manipulation des Heaps die Kontrolle über den Programmfluss erlangen konnten. Sie überschrieben kritische Datenstrukturen im Speicher und führten so schädlichen Code aus

Solche Angriffe können schwerwiegende Folgen haben, einschließlich Datenverlust, unbefugtem Zugriff auf Systeme und der Ausführung von Schadsoftware.

Wie liegen diese Kontrollstrukturen im Speicher vor?

Kontrollstrukturen wie Schleifen, Bedingungen und Funktionsaufrufe werden im Speicher durch den Programmcode und die zugehörigen Datenstrukturen repräsentiert. Hier ist eine kurze Übersicht, wie sie im Speicher organisiert sind:

  1. Programmcode: Der eigentliche Code der Kontrollstrukturen wird im Textsegment des Speichers abgelegt. Dies umfasst die Anweisungen, die der Prozessor ausführt.
  2. Stack: Der Stack-Speicher wird verwendet, um lokale Variablen, Funktionsaufrufe und Rücksprungadressen zu speichern. Wenn eine Funktion aufgerufen wird, werden die Parameter und die Rücksprungadresse auf den Stack gelegt. Bei Schleifen und Bedingungen werden die aktuellen Zustände und Variablen ebenfalls auf dem Stack verwaltet.
  3. Heap: Dynamisch zugewiesene Speicherbereiche, die durch Funktionen wie malloc() angefordert werden, befinden sich im Heap. Kontrollstrukturen selbst nutzen den Heap nicht direkt, aber die Daten, die sie verarbeiten, können dort gespeichert sein.

Ein Beispiel für eine Sicherheitslücke durch einen Heap Overflow ist, wenn ein Angreifer den Heap so manipuliert, dass er die Kontrollstrukturen im Speicher überschreibt. Dadurch kann der Angreifer den Programmfluss ändern und schädlichen Code ausführen

Gibt es ein Beispiel, was eine Kontrollstruktur im Heap abspeichern könnte, was dazu führt dass sie manipuliert wird?

Ja, ein Beispiel für eine Kontrollstruktur, die im Heap gespeichert wird und manipuliert werden kann, sind Zeiger auf Funktionszeiger innerhalb von Datenstrukturen. Hier ist ein konkretes Szenario:

Stellen wir uns vor, ein Programm verwendet eine Datenstruktur, die einen Funktionszeiger enthält. Dieser Funktionszeiger zeigt auf eine Routine, die aufgerufen wird, wenn bestimmte Bedingungen erfüllt sind. Wenn ein Heap Overflow auftritt, kann ein Angreifer den Funktionszeiger überschreiben und ihn auf eine schädliche Routine umleiten.

Ein Beispiel für einen solchen Angriff ist der Heap Overflow Angriff auf den iOS-Kernel. In diesem Fall wurde der Heap so manipuliert, dass ein überlaufener Speicherbereich mit einem kritischen Datenobjekt kollidierte. Der Angreifer konnte dadurch den Funktionszeiger innerhalb des Datenobjekts überschreiben und die Kontrolle über den Programmfluss übernehmen.

In dem beschriebenen Szenario hat der Angreifer den Funktionszeiger im Heap-Speicherbereich überschrieben. Der Heap wird für dynamische Speicherzuweisungen verwendet, und in diesem Fall wurde ein Funktionszeiger innerhalb einer Datenstruktur im Heap manipuliert. Durch den Heap Overflow konnte der Angreifer den Funktionszeiger so ändern, dass er auf schädlichen Code zeigt, anstatt auf die ursprünglich vorgesehene Funktion.

Wo lag der schädliche Code, auf den der Funktionszeiger umgeschrieben wurde?

Der schädliche Code, auf den der Funktionszeiger umgeschrieben wurde, kann sich an verschiedenen Stellen im Speicher befinden. Häufig wird er jedoch im Heap oder im Textsegment des Speichers platziert.

Hier sind die beiden häufigsten Szenarien:

  1. Heap: Der Angreifer kann den schädlichen Code direkt im Heap platzieren, indem er eine übermäßige Eingabe sendet, die den Heap überläuft und den Funktionszeiger überschreibt. Der Funktionszeiger wird dann auf den schädlichen Code im Heap umgeleitet.
  2. Textsegment: In einigen Fällen kann der Angreifer den Funktionszeiger so manipulieren, dass er auf bereits vorhandenen schädlichen Code im Textsegment zeigt. Dies kann durch das Einfügen von Shellcode in den Speicher erreicht werden, der dann durch den manipulierten Funktionszeiger ausgeführt wird

Kann man sich auf seinem Rechner den Heap anzeigen lassen?

Es ist möglich, den Heap-Speicherinhalt auf seinem Rechner anzuzeigen, allerdings erfordert dies spezielle Tools und Kenntnisse. Hier sind einige Methoden, wie der Heap-Speicher untersucht werden kann:

  1. Debugger: Mit Debuggern wie GDB (GNU Debugger) oder WinDbg (Windows Debugger) kann man den Speicher eines laufenden Programms untersuchen. Diese Tools ermöglichen es dir, den Heap-Speicher zu durchsuchen und zu analysieren.
  2. Heap-Profiler: Tools wie Valgrind (insbesondere das Modul Massif) oder Visual Studio Profiler können verwendet werden, um den Heap-Speicher zu profilieren und Speicherlecks sowie Speicherüberläufe zu identifizieren.
  3. Speicher-Dump-Analyse: Mit einem Speicher-Dump (Abbild des Speichers) eines laufenden Programms erstellen und diesen mit Tools wie WinDbg oder GDB analysieren. Dies ermöglicht, den Zustand des Heaps zu einem bestimmten Zeitpunkt zu untersuchen.

Hier ist ein einfaches Beispiel, wie man mit GDB den Heap-Speicher eines Programms untersuchen kannst:

gdb ./das_programm
(gdb) run
(gdb) info proc mappings
(gdb) x/20xw 0xheap_start_address

In diesem Beispiel ersetzt man./das_programm durch den Namen des Programms und 0xheap_start_address durch die Startadresse des Heaps, die aus den Speicherzuordnungen kommt.

Wie findet man eine Benutzereingabe, die zu einem Heap Overflow führt?

Das Finden einer Benutzereingabe, die zu einem Heap Overflow führt, ist eine komplexe Aufgabe und erfordert ein tiefes Verständnis des Zielprogramms sowie der Art und Weise, wie es Speicher verwaltet. Hier sind einige Schritte, die oft verwendet werden:

  1. Quellcode-Analyse: Durchsuche den Quellcode des Programms nach Stellen, an denen dynamischer Speicher zugewiesen wird (z.B. durch malloc()calloc()realloc()). Achte besonders auf Funktionen, die Benutzereingaben verarbeiten.
  2. Fuzzing: Verwende Fuzzing-Tools, um das Programm mit zufälligen oder speziell gestalteten Eingaben zu testen. Fuzzing kann helfen, Schwachstellen zu finden, indem es das Programm mit einer Vielzahl von Eingaben bombardiert und nach Abstürzen oder ungewöhnlichem Verhalten sucht. Beispiele für Fuzzing-Tools sind AFL (American Fuzzy Lop) und LibFuzzer.
  3. Manuelle Tests: Erstelle manuell Eingaben, die die Grenzen der Puffer überschreiten könnten. Dies kann durch das Senden von sehr langen Zeichenketten oder durch das Einfügen spezieller Zeichenfolgen geschehen, die das Programm möglicherweise nicht korrekt verarbeitet.
  4. Debugging: Verwende Debugger wie GDB oder WinDbg, um das Programm während der Ausführung zu überwachen. Setze Breakpoints an kritischen Stellen und beobachte, wie das Programm auf verschiedene Eingaben reagiert. Achte auf Speicherüberläufe und überprüfe, ob der Heap beschädigt wird.
  5. Speicheranalyse-Tools: Nutze Tools wie Valgrind oder AddressSanitizer, um Speicherprobleme zu erkennen. Diese Tools können helfen, Speicherlecks, Überläufe und andere Speicherprobleme zu identifizieren.

Hier ist ein einfaches Beispiel für Fuzzing mit AFL:

# Installiere AFL
sudo apt-get install afl

# Instrumentiere das Zielprogramm
afl-gcc -o zielprogramm zielprogramm.c

# Führe AFL aus
afl-fuzz -i input_dir -o output_dir ./zielprogramm

Gibt es ein Beispielcode in C oder C++, wie man einen Heap Overflow verursachen kann?

Dieser Code sollte nur zu Lernzwecken dienen und nicht in einer produktiven Umgebung verwendet werden, da er Sicherheitsrisiken birgt.

Hier ist ein Beispielcode:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void vulnerable_function(const char *input) {
    // Allokiere einen Puffer von 10 Bytes auf dem Heap
    char *buffer = (char *)malloc(10 * sizeof(char));
    if (buffer == NULL) {
        fprintf(stderr, "Speicherzuweisung fehlgeschlagen\n");
        exit(1);
    }

    // Kopiere die Eingabe in den Puffer ohne Größenüberprüfung
    strcpy(buffer, input);

    // Ausgabe des Puffers
    printf("Pufferinhalt: %s\n", buffer);

    // Freigabe des Puffers
    free(buffer);
}

int main(int argc, char *argv[]) {
    if (argc < 2) {
        fprintf(stderr, "Verwendung: %s <Eingabe>\n", argv[0]);
        return 1;
    }

    // Aufruf der anfälligen Funktion mit Benutzereingabe
    vulnerable_function(argv[1]);

    return 0;
}

In diesem Beispiel wird ein Puffer von 10 Bytes auf dem Heap allokiert. Die Funktion strcpy kopiert die Benutzereingabe in diesen Puffer, ohne die Größe der Eingabe zu überprüfen. Wenn die Eingabe länger als 10 Bytes ist, wird der Puffer überlaufen, was zu einem Heap Overflow führt.

Mann kann dieses Programm kompilieren und ausführen, um das Verhalten zu beobachten:

gcc -o heap_overflow_example heap_overflow_example.c
./heap_overflow_example "Dies ist eine sehr lange Eingabe, die den Puffer überläuft"

Dies wird zu einem Heap Overflow führen und möglicherweise das Programm zum Absturz bringen oder unerwartetes Verhalten verursachen.

Kann dieses Programm auch Speicherbereiche anderer Programme überschreiben und diese manipulieren?

Nein, dieses Programm kann nicht direkt Speicherbereiche anderer Programme überschreiben und manipulieren. In modernen Betriebssystemen gibt es Schutzmechanismen, die verhindern, dass ein Programm auf den Speicherbereich eines anderen Programms zugreift. Diese Schutzmechanismen umfassen:

  1. Speicherschutz: Betriebssysteme wie Windows, Linux und macOS verwenden Speicherschutzmechanismen, um sicherzustellen, dass jedes Programm nur auf seinen eigenen Speicherbereich zugreifen kann. Versuche, auf den Speicherbereich eines anderen Programms zuzugreifen, führen zu einer Speicherzugriffsverletzung (Segmentation Fault) und dem Absturz des Programms.
  2. Adressraum-Layout-Randomisierung (ASLR): ASLR ist eine Sicherheitsfunktion, die die Speicheradressen von Programmcode, Daten und Bibliotheken zufällig anordnet. Dies erschwert es Angreifern, vorherzusagen, wo sich bestimmte Speicherbereiche befinden, und macht Exploits schwieriger.
  3. Benutzer- und Kernel-Modus: Betriebssysteme trennen den Speicher in Benutzer- und Kernel-Modus. Programme laufen im Benutzermodus und haben keinen direkten Zugriff auf den Kernel-Speicherbereich, was die Sicherheit weiter erhöht.

Ein Heap Overflow innerhalb eines Programms kann jedoch dazu führen, dass das Programm selbst abstürzt oder unerwartetes Verhalten zeigt. In einem Szenario, in dem ein Angreifer den Heap Overflow ausnutzt, könnte der Angreifer schädlichen Code innerhalb des betroffenen Programms ausführen, aber nicht direkt andere Programme beeinflussen.

Die Regeln in einem Rot-Schwarz-Baum

Eine Einführung in die Eigenschaften und Funktionsweise

Ein Rot-Schwarz-Baum ist eine spezielle Art von selbstbalancierendem binären Suchbaum, der in der Informatik weit verbreitet ist. Er wurde entwickelt, um das Einfügen, Löschen und Suchen von Elementen in logarithmischer Zeit zu ermöglichen. Die wichtigsten Eigenschaften von Rot-Schwarz-Bäumen sind ihre Balance und die Tatsache, dass sie eine garantierte Worst-Case-Performance bieten. Die Regeln, die einen Rot-Schwarz-Baum definieren, sind entscheidend für seine Funktionsweise.

Grundregeln eines Rot-Schwarz-Baums

Ein Rot-Schwarz-Baum hält sich an fünf grundlegende Regeln, die sicherstellen, dass der Baum immer balanciert bleibt. Diese Regeln sind:

1. Jeder Knoten ist entweder rot oder schwarz.

Jeder Knoten eines Rot-Schwarz-Baums hat eine Farbeigenschaft, die entweder rot oder schwarz sein kann. Diese Eigenschaft ist entscheidend, um die Struktur und Balance des Baums zu erhalten.

2. Die Wurzel ist immer schwarz.

Die Wurzel des Baums muss immer schwarz sein. Diese Regel stellt sicher, dass der Baum im Gleichgewicht bleibt und dass die Pfadlänge von der Wurzel zu jedem Blattknoten konsistent bleibt.

3. Alle Blätter (Nil-Knoten) sind schwarz.

In einem Rot-Schwarz-Baum sind alle Blätter, die als Nil-Knoten bezeichnet werden und keine Daten speichern, immer schwarz. Diese Regel hilft, die Struktur des Baums zu vereinheitlichen.

4. Rote Knoten haben keine roten Kinder (keine zwei aufeinanderfolgenden roten Knoten).

Ein roter Knoten darf keine roten Kinder haben. Dies bedeutet, dass in einem Rot-Schwarz-Baum keine zwei roten Knoten aufeinanderfolgen dürfen. Diese Regel verhindert, dass der Baum aus dem Gleichgewicht gerät.

5. Jeder Pfad von einem Knoten zu seinen Nil-Knoten-Blättern enthält die gleiche Anzahl schwarzer Knoten.

Diese Regel, auch als Schwarzhöhenregel bekannt, stellt sicher, dass die Anzahl der schwarzen Knoten auf jedem Pfad von einem Knoten zu seinen Nachkommen konsistent ist. Diese Konsistenz ist entscheidend für die Balance des Baums.

Operationen in einem Rot-Schwarz-Baum

Die Einhaltung der oben genannten Regeln ist entscheidend für die Durchführung von Operationen im Rot-Schwarz-Baum. Zu den wichtigsten Operationen gehören das Einfügen, Löschen und Suchen von Knoten. Jede dieser Operationen muss sicherstellen, dass die Regeln des Rot-Schwarz-Baums nach ihrer Durchführung weiterhin gültig sind.

1. Einfügen

Beim Einfügen eines neuen Knotens in einen Rot-Schwarz-Baum wird der neue Knoten initial als rot markiert. Dies geschieht, um sicherzustellen, dass die Schwarzhöhenregel nicht verletzt wird. Nach dem Einfügen wird der Baum rebalanciert und die Farben der Knoten werden angepasst, um die Rot-Schwarz-Regeln zu erfüllen. Dies kann Rotationen und Farbänderungen der Knoten erfordern.

2. Löschen

Das Löschen eines Knotens aus einem Rot-Schwarz-Baum ist komplexer als das Einfügen. Es erfordert, dass der Baum rebalanciert wird, um die Rot-Schwarz-Regeln nach dem Löschen aufrechtzuerhalten. Wenn der zu löschende Knoten schwarz ist, kann dies die Schwarzhöhenregel verletzen, und zusätzliche Schritte wie Rotationen und Farbänderungen sind notwendig, um das Gleichgewicht wiederherzustellen.

3. Suchen

Das Suchen in einem Rot-Schwarz-Baum folgt denselben Prinzipien wie das Suchen in einem gewöhnlichen binären Suchbaum. Die Suchoperation ist effizient aufgrund der garantierten logarithmischen Höhe des Baums, die durch die Rot-Schwarz-Regeln gewährleistet wird.

Beispiele und Anwendungen

Rot-Schwarz-Bäume finden in vielen Bereichen der Informatik Anwendung. Sie werden häufig in der Implementierung von assoziativen Arrays, symbolischen Tabellen und Priority Queues verwendet. Ihre Eigenschaften machen sie ideal für Situationen, in denen konsistente Leistung und effiziente Operationen erforderlich sind.

Ein Beispiel für die Anwendung von Rot-Schwarz-Bäumen ist die Implementierung von Dictionaries in Programmiersprachen wie C++ (std::map) und Java (java.util.TreeMap). Diese Datenstrukturen basieren auf der Effizienz und Selbstbalancierungsfähigkeit von Rot-Schwarz-Bäumen.

Fazit

Rot-Schwarz-Bäume sind eine leistungsstarke Datenstruktur, die durch ihre spezifischen Regeln eine effiziente und balancierte Organisation von Daten ermöglicht. Das Verständnis und die Einhaltung dieser Regeln sind entscheidend für die Implementierung und Nutzung von Rot-Schwarz-Bäumen in der Informatik. Ihre Anwendungen und Vorteile machen sie zu einem unverzichtbaren Werkzeug für Entwickler und Ingenieure, die effiziente Datenstrukturen benötigen.

Theme Songs aktueller Kinderserien: Super Wings Theme, Top Wing Theme, Paw Patrol und Feuerwehrmann Sam teilweise mit Tabulaturen / Guitar und Bass Tabs inklusive der englischen Texte / Lyrics

Intention

Wer durch Top Wing oder Super Wings (Super RTL / Kika) einen Ohrwurm hat und das gerne mal nachspielen möchte, der kann sich gerne mal meine 2 neuen YouTube-Videos anschauen.

Aktuelle Kinderserien setzen zur Zeit meistens auf instrumentale Rock-Themes anstelle von Synthesizer-Musik.

Duck Tales fand ich früher auch immer cool, bin aber noch nicht dazu gekommen ;-).

Text / Lyrics

Den Text habe ich im Video selber eingebaut.

Tabulaturen

Die Tabs befinden sich in der Description der YouTube-Videos. Am Besten also das Video durch klick auf den Text „YouTube“ im hier eingebetteten Player klicken und die Description öffnen, falls diese sehen möchte.

Top Wing (Video)

Super Wings (Video)

Paw Patrol [Parody: Pub Patrol] (Video)

Hier noch ein älteres Video von mir ohne Tabs …

Feuerwehrmann Sam [Metal Version ohne Gesang / Tabs] (Video)

Und noch ein ganz altes Video 🙂 …

Algorithmen und Datenstrukturen: Der Radix Sort in Java

Der Algorithmus

Der Radix Sort-Algorithmus sortiert Zahlensysteme anhand ihrer Stellen. Der Radix Sort wird daher auch Base Sort genannt. Dies bedeutet, dass je Stelle ein eigenes Sortierverfahren (zumeist Counting Sort weil Wertebereich überschaubar) eingesetzt wird. Man würde also bei 3 Stellen auch 3x sortieren.

Es gibt einen Most- und Least-Significant-Radix-Sort (MSD / LSD Radix Sort). LSD beginnt bei der niedrigsten Stelle (z.B. den Einern) und bewegt sich zu den höheren Stellen (z.B. Zehner, Hunderter). Bei MSD Radix Sort ist das umgekehrt.

Eine wichtige Voraussetzung ist, das man die gleiche Anzahl an Stellen hat (also z.B. 2 (Tupel), 3 (Tripel) oder mehr Stellen). Weiterhin müssen die vorhandenen Elemente in dem Zahlensystem (z.B. Dezimal 0-9) in einer Reihenfolge nach Rang sortierbar sein. D.h. es sollte z.B. klar sein dass ein A vor einem B ist (z.B. durch ASCII-Werte).

Nehmen wir an, wir möchten die Zahlen [170, 45, 75, 90, 802, 24, 2, 66] sortieren:

LSD Radix Sort (von rechts nach links):

  1. Sortierung nach der 1er-Stelle: [170, 90, 802, 2, 24, 45, 75, 66]
  2. Sortierung nach der 10er-Stelle: [802, 2, 24, 45, 66, 170, 75, 90]
  3. Sortierung nach der 100er-Stelle: [2, 24, 45, 66, 75, 90, 170, 802]

    Anwendung: Oft bei der Sortierung von Zahlen und Wörtern verwendet.
    Vorteil: Einfacher zu implementieren und erfordert weniger komplexe Vergleiche.

MSD Radix Sort (von links nach rechts):

  1. Sortierung nach der 100er-Stelle: [170, 24, 2, 45, 66, 75, 802, 90]
  2. Sortierung nach der 10er-Stelle: [2, 24, 45, 66, 75, 90, 170, 802]
  3. Sortierung nach der 1er-Stelle: [2, 24, 45, 66, 75, 90, 170, 802]

    Anwendung: Eignet sich gut für große Zahlenmengen oder lange Zeichenketten.
    Vorteil: Kann effizienter sein, wenn die Daten ungleichmäßig verteilt sind.

Code von LSD Radix Sort

Der folgende Code hat die vergangenen Implementierungen von QuickSort und Counting Sort (ohne Stellensortierung durch Radix / Base Sort) mit einer Zeitmessung in Echtzeit verglichen und muss angepasst werden. Das nachfolgende Beispiel sortiert Dezimalzahlen (also ein Zahlensystem zur Basis 10).

package AlgoDat;

import java.util.Arrays;

public class RadixSort {
    // Zu sortierendes Array
    private static int myArrayRadixSort[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
    
    public boolean verbose = false;

    // Hält die Klassen als instanziertes Objekt
    @SuppressWarnings("unused")
    private static RadixSort programRadixSort;
    @SuppressWarnings("unused")
    private static HelperUtil helper;

    // Hilfsfunktion für das Ausgeben des Arrays
    public void OutputOfIntArray(int myArray[])
    {
        if (myArray != null)
        {
            for (int i = 0; i < myArray.length; i++) {
                if (i > 0) System.out.print(";");
                System.out.print(myArray[i]);
            }

            System.out.println();
        }
    }

    public void radixSort(int[] arr) 
    { 
        int max = Arrays.stream(arr).max().getAsInt();
        if (verbose) System.out.println("Größte Zahl im Array: " + max);
        
        // Bei Dezimalzahlen muss die Basis 10 genommen werden
        // ... bei Großbuchstaben z.B. die Basis 27
        for (int exp = 1; max / exp > 0; exp *= 10) 
        { 
            if (verbose) System.out.println("Suche " + exp + "er.");
            countingSort(arr, exp); 
        } 
    } 
    
    public void countingSort(int[] arr, int exp) 
    { 
        int n = arr.length; 
        int[] output = new int[n]; 
        int[] count = new int[10]; 
        
        // Alle 10 Elemente mit 0 initialisieren
        for (int i = 0; i < 10; i++) 
        { 
            count[i] = 0; 
        } 
        
        // Histogramm erstellen
        for (int i = 0; i < n; i++) 
        { 
            count[(arr[i] / exp) % 10]++; 
        } 
        
        // Kummuliere, so dass die Anfangspositionen in dem Array stehen
        for (int i = 1; i < 10; i++) 
        { 
            count[i] += count[i - 1]; 
        } 
        
        // Ausgabearray erstellen
        for (int i = n - 1; i >= 0; i--) 
        { 
            output[count[(arr[i] / exp) % 10] - 1] = arr[i]; 
            count[(arr[i] / exp) % 10]--; 
        } 
        
        // Kopiere das neu erstellte Array auf das zu ändernde Array
        for (int i = 0; i < n; i++) 
        { 
            arr[i] = output[i]; 
        } 
    } 
    
    // Konstruktor
    public RadixSort(int[] toSort)
    {
        this.radixSort(toSort);
    }

    // Konstruktor
    public RadixSort()
    {
        System.out.print("Vorher: ");
        this.OutputOfIntArray(myArray);

        this.radixSort(myArray); 
        
        System.out.print("Nachher: ");
        this.OutputOfIntArray(myArray);
    }

    public static void main(String[] args) 
    {
        helper = new HelperUtil();

        // Es gibt 80 Mio Menschen in Deutschland, von denen keiner älter als 120 ist -> Kleiner Wertebereich
        int[] alterDerMenschenInDeutschlandRS = helper.generateIntegerArrayOfSize(80000000, 120);
        int[] alterDerMenschenInDeutschlandQS = alterDerMenschenInDeutschlandRS.clone();
        int[] alterDerMenschenInDeutschlandCS = alterDerMenschenInDeutschlandRS.clone();
        // Erwartung: Da Counting Sort eine lineare Laufzeit hat sollte er bei kleinem Wertebereich am Besten performen
        
        System.out.println("\nEs gibt 80 Mio Menschen in Deutschland, von denen keiner älter als 120 ist -> Kleiner Wertebereich");
        System.out.println("===================================================================");
        
        long startZeitRS = System.nanoTime();
        programRadixSort = new RadixSort(alterDerMenschenInDeutschlandRS);
        long endZeitRS = System.nanoTime();
        System.out.println((endZeitRS-startZeitRS) + " ns (Radix Sort)");
    }
}

Ausgabe

Es gibt 80 Mio Menschen in Deutschland, von denen 
keiner älter als 120 ist -> Kleiner Wertebereich
=======================================================
347584000 ns (Counting Sort)
2544168000 ns (Radix Sort)
3335958900 ns (Quick Sort)

Komplexität: O-Notation (Ordnung)

O(n*l) (l=Länge also bei ABC = Länge: 3 – Anzahl der max. Stellen0)
‣ Sortieren von Strings über einem endlichen Alphabet durch
mehrmaliges Anwenden von Counting Sort.
‣ Angenommen: Alle Wörter haben die Länge
‣ Z.b. Postleitzahlen

Laufzeit von Radix Sort: 𝒪(n), weil l ⋅ n Durchläufe

Algorithmen und Datenstrukturen: Der Counting Sort in Java

Der Algorithmus

Der Counting Sort ist ein Out-of-place-Sortieralgorithmus, da er das zu sortierende Array im Gegensatz zu Quick Sort oder Bubble Sort nicht direkt sortiert, sondern vorher eine Speicherkopie anlegt, die im Abschluss auf das zu sortierende Array kopiert wird.

Der Algorithmus ist genau dann effizient, wenn man viele (doppelte) Zahlen in einem kleinem Wertebereich / einer engen Min-/Max-Range sortieren möchte.

Wenn man z.B. ein Array mit dem Aufkommen von Menschen nach Alter in der deutschen Bevölkerung sortieren möchte, so hätte man eine Array-Größe von ca. 80 Millionen Einträgen. Da es aber keine Menschen über 120 Jahren in Deutschland gibt, oder der älteste noch lebende Mensch in Deutschland aktuell jünger als 120 Jahre ist, kann man den Wertebereich zwischen 0 und 120 Jahren einschränken.

  • Kleiner Wertebereich: Alter zwischen 0 und 120 Jahren.
  • Großes Array: 80 Millionen Einträge für jeden Menschen

Für diese Fälle eignet sich der Counting Sort Algorithmus ausgezeichnet, da er nach der folgenden Vorgehensweise vor geht:

  • Ermittle den maximalen Wert des Wertebereichs für das Histogramm (z.B. höchstes Alter 120 Jahre)
  • Initialisiere ein sortiertes Histogramm als Array mit 0-Werten.
  • Laufe das große Array in einer O(n)-Schleife durch (z.B. das Array mit den 80 Mio. Menschen)
    • Zähle die Histogramm-Array-Werte über die Vorkommnisse/Häufigkeiten beim Durchlaufen um 1 nach oben, je nachdem welche Zahl bei dem Durchlauf gefunden wird
    • Laufe das erstellte Histogramm-Array von links nach rechts durch und füge die Vorkommnisse der Zahlen in das Ziel-Array ein, so dass bei 2x der Zahl 1 und 4x der Zahl 2 so etwas rauskommt: 1;1;2;2;2;2
  • Auf diese Weise wurde anhand des sortierten Histogramm-Arrays die Zahlenmenge sortiert
package AlgoDat;

import java.util.Arrays;

public class CountingSort {
    // Zu sortierendes Array
    private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};

    // Hält die Klasse als instanziertes Objekt
    @SuppressWarnings("unused")
    private static CountingSort program;
    private java.util.Random rnd = new java.util.Random();

    // Hilfsfunktion für das Ausgeben des Arrays
    public void OutputOfIntArray(int myArray[])
    {
        if (myArray != null)
        {
            for (int i = 0; i < myArray.length; i++) {
                if (i > 0) System.out.print(";");
                System.out.print(myArray[i]);
            }

            System.out.println();
        }
    }

    // Generiert ein zufälliges Integer-Array der Größe size mit Werten zwischen 0 und upperLimit
    public int[] generateIntegerArrayOfSize(int size, int upperLimit)
    {       
        int[] generatedArray = new int[size];
        
        for (int i = 0; i < generatedArray.length; i++)
        {
            generatedArray[i] = rnd.nextInt(upperLimit);
        }

        return generatedArray;
    }

    // Konstruktor
    public CountingSort()
    {
        System.out.println("Kleines Array");
        System.out.println("=============");
        System.out.print("Vorher: ");
        this.OutputOfIntArray(myArray);

        long startTime = System.nanoTime();
        this.sort(myArray, false);
        long endTime = System.nanoTime();

        System.out.print("Nachher: ");
        this.OutputOfIntArray(myArray);

        System.out.println("Ich habe " + (endTime-startTime) + " ns mit einem Array von " + myArray.length + " und einem Wertebereich/Histogramm von " + Arrays.stream(myArray).max().getAsInt() + " Zahlen gebraucht! \n\n");

        System.out.println("Großes Array, kleiner Wertebereich");
        System.out.println("==================================");
        System.out.print("Vorher: ");
        int[] grossesArray = this.generateIntegerArrayOfSize(10000000, 100000);

        startTime = System.nanoTime();
        this.sort(grossesArray, false);
        endTime = System.nanoTime();

        System.out.println("Ich habe " + (endTime-startTime) + " ns mit einem Array von " + grossesArray.length + " und einem Wertebereich/Histogramm von " + Arrays.stream(grossesArray).max().getAsInt() + " Zahlen gebraucht! \n\n");

        System.out.println("Kleines Array, großer Wertebereich");
        System.out.println("==================================");
        System.out.print("Vorher: ");
        int[] kleinesArray = this.generateIntegerArrayOfSize(100000, 10000000);

        startTime = System.nanoTime();
        this.sort(kleinesArray, false);
        endTime = System.nanoTime();

        System.out.println("Ich habe " + (endTime-startTime) + " ns mit einem Array von " + kleinesArray.length + " und einem Wertebereich/Histogramm von " + Arrays.stream(kleinesArray).max().getAsInt() + " Zahlen gebraucht! \n\n");
    }

    public void sort(int[] myArray) 
    {
        this.sort(myArray, true);
    }

    public void sort(int[] myArray, boolean verbose) 
    {
        //int maxValue = findMax(elements);
        int maxValue = Arrays.stream(myArray).max().getAsInt();
        int[] counts = new int[maxValue + 1];

        // Phase 1: Erstelle das Histogramm
        for (int element : myArray) 
        {
            counts[element]++;
        }

        if (verbose)
        {
            System.out.println("Erstelle Histogramm als Array mit den Häufigkeiten der Zahlen im Array");
        
            // Optional - kann auskommentiert werden: Headline von Histogramm und Ausgabe Histogramm
            for (int i = 0; i < maxValue; i++)
            {
                System.out.print(i);

                if (i + 1 != maxValue)
                {
                    System.out.print(";");
                }
            }

            System.out.println("");
            this.OutputOfIntArray(counts);
        }

        // Phase 2: Aggregiere die Zahlen, um die Startadressen in Zielarray zu ermitteln
        for (int i = 1; i <= maxValue; i++) 
        {
            // Die Daten im Array werden von links nach rechts kummuliert
            // um die Startadresse für jede Zahl zu bekommen.
            counts[i] += counts[i - 1];
        }

        if (verbose)
        {
            System.out.println("Array mit den aggregierten Zahlen (Histogramm) für die Startadresse im Zielarray:");
            this.OutputOfIntArray(counts);
        }

        // Phase 3: Schreibe die Zahlen ins Zielarray
        int[] target = new int[myArray.length];

        for (int i = myArray.length - 1; i >= 0; i--) 
        {
            int element = myArray[i];
            
            counts[element] = counts[element] - 1;

            if (verbose)
            {
                System.out.println("Schreibe " + element +" an Index " + counts[element] + " des zu sortierten Arrays!");
            }

            target[counts[element]] = element;
        }

        // Copy target back to input array
        System.arraycopy(target, 0, myArray, 0, myArray.length);
    } 

    public static void main(String[] args) 
    {
        // Instanziere aus den statischem Programm ein echtes Objekt
        // damit nicht alle Methoden und Variablen static sein müssen.
        program = new CountingSort();
    }
}

Ausgabe

Kleines Array
=============
Vorher: 22;6;2;4;10;3;9;7;5;8;1
Nachher: 1;2;3;4;5;6;7;8;9;10;22
Ich habe 12449300 ns mit einem Array von 11 und einem Wertebereich/Histogramm von 22 Zahlen gebraucht! 


Großes Array, kleiner Wertebereich (Ausgabe aus)
================================================
Ich habe 75933500 ns mit einem Array von 10000000 und einem Wertebereich/Histogramm von 99999 Zahlen gebraucht! 


Kleines Array, großer Wertebereich (Ausgabe aus)
================================================
Ich habe 25634500 ns mit einem Array von 100000 und einem Wertebereich/Histogramm von 9999905 Zahlen gebraucht! 

Komplexität: O-Notation (Ordnung)

Die Laufzeit der Funktion hängt von {\displaystyle n} (Anzahl der Elemente des Eingabearrays) und {\displaystyle k} (die Größe des Zahlenintervalls) ab. Die for-Schleifen werden jeweils {\displaystyle n}-mal oder {\displaystyle k}-mal durchlaufen. Die Zeitkomplexität von Countingsort beträgt somit {\displaystyle {\mathcal {O}}(n+k)}.

Algorithmen und Datenstrukturen: Notationen

Notationen

NotationDefinitionZweckBeispiel
O-Notation (Big O) Die O-Notation beschreibt das schlechteste Szenario der Laufzeit eines AlgorithmusSie gibt an, wie die Laufzeit eines Algorithmus im schlimmsten Fall wächst, wenn die Eingabegröße gegen unendlich geht.Wenn ein Algorithmus eine Laufzeit von O(n²) hat, bedeutet das, dass die Laufzeit im schlimmsten Fall quadratisch zur Eingabegröße n wächst.
Small-o-Notation (small o) Die Small-o-Notation beschreibt eine obere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die schlechteste Laufzeit ist. Sie gibt an, dass die Laufzeit eines Algorithmus asymptotisch kleiner ist als eine bestimmte Funktion.Sie wird verwendet, um zu zeigen, dass die Laufzeit eines Algorithmus schneller wächst als eine bestimmte Funktion, aber langsamer als eine andere.Wenn ein Algorithmus eine Laufzeit von o(n²) hat, bedeutet das, dass die Laufzeit asymptotisch kleiner ist als n², aber nicht notwendigerweise im schlimmsten Fall.
Omega-Notation (Big Ω)Die Omega-Notation beschreibt das beste Szenario der Laufzeit eines Algorithmus.Sie gibt an, wie die Laufzeit eines Algorithmus im besten Fall wächst, wenn die Eingabegröße gegen unendlich geht.Wenn ein Algorithmus eine Laufzeit von Ω(n) hat, bedeutet das, dass die Laufzeit im besten Fall linear zur Eingabegröße n wächst.
Kleine Omega-Notation (kleines ω)Die kleine Omega-Notation beschreibt eine untere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die beste Laufzeit ist. Sie gibt an, dass die Laufzeit eines Algorithmus asymptotisch größer ist als eine bestimmte Funktion.Sie wird verwendet, um zu zeigen, dass die Laufzeit eines Algorithmus langsamer wächst als eine bestimmte Funktion, aber schneller als eine andere.Wenn ein Algorithmus eine Laufzeit von ω(n) hat, bedeutet das, dass die Laufzeit asymptotisch größer ist als n, aber nicht notwendigerweise im besten Fall.
Theta-Notation (Θ)Die Theta-Notation beschreibt sowohl die obere als auch die untere Schranke der Laufzeit eines Algorithmus. Sie gibt an, dass die Laufzeit eines Algorithmus asymptotisch zwischen zwei Funktionen liegt.Sie wird verwendet, um die genaue Wachstumsrate der Laufzeit eines Algorithmus zu beschreiben, indem sie sowohl das beste als auch das schlechteste Szenario berücksichtigt.Wenn ein Algorithmus eine Laufzeit von Θ(n²) hat, bedeutet das, dass die Laufzeit asymptotisch sowohl durch n² nach oben als auch nach unten beschränkt ist.

Exakte Wachstumsrate (sowohl obere als auch untere Schranke)
Notationen (tabellarisch)

O-Notation (Big O)

  • Zweck: Beschreibt das schlechteste Szenario der Laufzeit eines Algorithmus. Sie gibt an, wie die Laufzeit im schlimmsten Fall wächst, wenn die Eingabegröße gegen unendlich geht.

Omega-Notation (Big Ω)

  • Zweck: Beschreibt das beste Szenario der Laufzeit eines Algorithmus. Sie gibt an, wie die Laufzeit im besten Fall wächst, wenn die Eingabegröße gegen unendlich geht.

Small-o-Notation (kleines o)

  • Zweck: Beschreibt eine obere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die schlechteste Laufzeit ist. Sie zeigt, dass die Laufzeit asymptotisch kleiner ist als eine bestimmte Funktion.

Theta-Notation (Θ)

  • Zweck: Beschreibt sowohl die obere als auch die untere Schranke der Laufzeit eines Algorithmus. Sie gibt die genaue Wachstumsrate der Laufzeit an, indem sie sowohl das beste als auch das schlechteste Szenario berücksichtigt.

Kleine Omega-Notation (kleines ω)

  • Zweck: Beschreibt eine untere Schranke für die Laufzeit eines Algorithmus, die jedoch nicht notwendigerweise die beste Laufzeit ist. Sie zeigt, dass die Laufzeit asymptotisch größer ist als eine bestimmte Funktion.

Algorithmen und Datenstrukturen: Der optimierte Bubble Sort in Java

Der Algorithmus

Dieser Algorithmus ist eine Erweiterung des normalen Bubble Sort Algorithmus. Wie dieser wird hierbei ein Array durchlaufen und das Element der aktuellen Iteration mit dem Nachfolgeelement getauscht, wenn dieses kleiner ist. Dadurch blubbern die Zahlen vom Array-Anfang bis zum Ende in einen sortierten Bereich auf der rechten Seite des Arrays nach oben.

Der optimierte Bubble Sort-Algorithmus bricht weitere Iterationen ab, wenn er in in seiner if-Bedingung nichts mehr zum Tauschen gefunden hat. Dies vermerkt er in einer bool-Variable, was die umgebende do…while-Schleife nutzt um den Algorithmus abzubrechen.

package AlgoDat;
 
public class OptimizedBubbleSort {
    // Zu sortierendes Array
    private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
 
    // Hält die Klasse als instanziertes Objekt
    @SuppressWarnings("unused")
    private static OptimizedBubbleSort program;
 
    // Hilfsfunktion für das Ausgeben des Arrays
    public void OutputOfIntArray(int myArray[])
    {
        if (myArray != null)
        {
            for (int i = 0; i < myArray.length; i++) {
                if (i > 0) System.out.print(";");
                System.out.print(myArray[i]);
            }
 
            System.out.println();
        }
    }
 
    // Konstruktor
    public OptimizedBubbleSort()
    {
        System.out.print("Vorher: ");
        this.OutputOfIntArray(myArray);
 
        // Da wir eine do .. while-Schleife nun nutzen,
        // zählen wir einen Index darin runter um diesen
        // im Array jederzeit adressieren zu können.
        int sortierterBereichRechts = myArray.length;
 
        // Wenn in einer Iteration nix getauscht wurde
        // wird das für alle weiteren auch der Fall sein.
        // In dem Fall kann der Algorithmus enden.
        boolean hatteNochWasZuTun = false;
 
        do
        {
            // Am Anfang gibts nix zu tun
            hatteNochWasZuTun = false;   
 
            System.out.println("Iteration: " + (myArray.length - sortierterBereichRechts + 1));
 
            for (int i = 0; i < sortierterBereichRechts - 1; i++)
            {
                if (myArray[i] > myArray[i + 1])
                {
                    this.vertausche(myArray, i, i + 1);
                    System.out.print("Tausche: ");
                    this.OutputOfIntArray(myArray);
                    hatteNochWasZuTun = true;
                }
            }
             
            // Der sortierte Bereich wächst
            sortierterBereichRechts--;
        }
        while (hatteNochWasZuTun);
 
        System.out.print("Nachher: ");
        this.OutputOfIntArray(myArray);
    }
 
    public void vertausche(int[] arrayToSwap, int idx1, int idx2)
    {
        int swapVar = arrayToSwap[idx1];
        arrayToSwap[idx1] = arrayToSwap[idx2];
        arrayToSwap[idx2] = swapVar;
    }
 
    public static void main(String[] args) 
    {
        // Instanziere aus den statischem Programm ein echtes Objekt
        // damit nicht alle Methoden und Variablen static sein müssen.
        program = new OptimizedBubbleSort();
    }
}

Ausgabe

Vorher: 22;6;2;4;10;3;9;7;5;8;1
Iteration: 1
Tausche: 6;22;2;4;10;3;9;7;5;8;1
Tausche: 6;2;22;4;10;3;9;7;5;8;1
Tausche: 6;2;4;22;10;3;9;7;5;8;1
Tausche: 6;2;4;10;22;3;9;7;5;8;1
Tausche: 6;2;4;10;3;22;9;7;5;8;1
Tausche: 6;2;4;10;3;9;22;7;5;8;1
Tausche: 6;2;4;10;3;9;7;22;5;8;1
Tausche: 6;2;4;10;3;9;7;5;22;8;1
Tausche: 6;2;4;10;3;9;7;5;8;22;1
Tausche: 6;2;4;10;3;9;7;5;8;1;22
Iteration: 2
Tausche: 2;6;4;10;3;9;7;5;8;1;22
Tausche: 2;4;6;10;3;9;7;5;8;1;22
Tausche: 2;4;6;3;10;9;7;5;8;1;22
Tausche: 2;4;6;3;9;10;7;5;8;1;22
Tausche: 2;4;6;3;9;7;10;5;8;1;22
Tausche: 2;4;6;3;9;7;5;10;8;1;22
Tausche: 2;4;6;3;9;7;5;8;10;1;22
Tausche: 2;4;6;3;9;7;5;8;1;10;22
Iteration: 3
Tausche: 2;4;3;6;9;7;5;8;1;10;22
Tausche: 2;4;3;6;7;9;5;8;1;10;22
Tausche: 2;4;3;6;7;5;9;8;1;10;22
Tausche: 2;4;3;6;7;5;8;9;1;10;22
Tausche: 2;4;3;6;7;5;8;1;9;10;22
Iteration: 4
Tausche: 2;3;4;6;7;5;8;1;9;10;22
Tausche: 2;3;4;6;5;7;8;1;9;10;22
Tausche: 2;3;4;6;5;7;1;8;9;10;22
Iteration: 5
Tausche: 2;3;4;5;6;7;1;8;9;10;22
Tausche: 2;3;4;5;6;1;7;8;9;10;22
Iteration: 6
Tausche: 2;3;4;5;1;6;7;8;9;10;22
Iteration: 7
Tausche: 2;3;4;1;5;6;7;8;9;10;22
Iteration: 8
Tausche: 2;3;1;4;5;6;7;8;9;10;22
Iteration: 9
Tausche: 2;1;3;4;5;6;7;8;9;10;22
Iteration: 10
Tausche: 1;2;3;4;5;6;7;8;9;10;22
Iteration: 11
Nachher: 1;2;3;4;5;6;7;8;9;10;22

Komplexität: O-Notation (Ordnung)

Worst- und Average-Case

Wie beim normalen Bubble Sort beträgt die Laufzeit-Komplexität im normalen und durchschnittlichen Fall O(n²).

Best-Case

Im Best-Case bricht der Algorithmus aber bereits nach einer Iteration ab, was einer Laufzeitkomplexität von O(n) entspricht.

Algorithmen und Datenstrukturen: Der „Randomized Single-Pivot QuickSort“ in Java

Der Algorithmus

Der QuickSort-Algorithmus ist ein rekursiver Sortieralgorithmus nach dem Teile- und Herrsche-Prinzip. Er ruft sich so lange selber auf, bis alle Array-Elemente auf der linken und rechten Stack-Seite eines Pivot-Elements sortiert sind. Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt. Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.

Anschließend muss man also noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so weiter. Diese Selbstaufrufe werden als Rekursion bezeichnet. Wenn eine Teilliste der Länge eins oder null auftritt, so ist diese bereits sortiert und es erfolgt der Abbruch der Rekusion.

Der Prinzip:

  1. Auswahl eine zufälligen Pivot-Elements (muss nicht das kleinste Element im Array sein)
  2. Sortierung aller kleineren Zahlen als das Pivot-Element auf die linke Seite des Stapels/Stacks
  3. Sortierung aller größeren Zahlen als das Pivot-Element auf die rechte Seite des Stapels/Stacks
  4. Rekursiver Aufruf für die linke Seite des Stapels/Stacks bis sich die zwei Left- und Right-Pointer überschneiden, weil keine kleinere Zahl mehr gefunden wurde, die links vom Pivot-Element einsortiert werden kann.
  5. Rekursiver Aufruf für die rechte Seite des Stapels/Stacks bis sich die zwei Left- und Right-Pointer überschneiden, weil keine größere Zahl mehr gefunden wurde, die rechts vom Pivot-Element einsortiert werden kann.
package AlgoDat;
 
public class QuickSort {
    // Zu sortierendes Array
    private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
 
    // Hält die Klasse als instanziertes Objekt
    @SuppressWarnings("unused")
    private static QuickSort program;
    private java.util.Random rnd = new java.util.Random();
 
    // Hilfsfunktion für das Ausgeben des Arrays
    public void OutputOfIntArray(int myArray[])
    {
        if (myArray != null)
        {
            for (int i = 0; i < myArray.length; i++) {
                if (i > 0) System.out.print(";");
                System.out.print(myArray[i]);
            }
 
            System.out.println();
        }
    }
 
    // Generiert ein zufälliges Integer-Array der Größe size mit Werten zwischen 0 und upperLimit
    public int[] generateIntegerArrayOfSize(int size, int upperLimit)
    {       
        int[] generatedArray = new int[size];
         
        for (int i = 0; i < generatedArray.length; i++)
        {
            generatedArray[i] = rnd.nextInt(upperLimit);
        }
 
        return generatedArray;
    }
 
    public void makeQuickSort(int[] arrayToSort, int fromIndex, int toIndex)
    {
        // Rekursionsabbruch
        if (fromIndex >= toIndex)
        {
            return;
        }
 
        // Das Pivot-Element muss beim Teile-Herrsche-Prinzip nicht die kleinste Zahl im Array sein 
        // und kann willkürlich gewählt werden - wie hier das letzte Element des Array
        int pivot = arrayToSort[toIndex];
        // Im Average Case performt der Quicksort aber besser, wenn es zufällig ausgewählt wird
        // int pivotIndex = rnd.nextInt(toIndex - fromIndex) + fromIndex;
        // int pivot = arrayToSort[pivotIndex];
 
        // Diese Pointer beinhalten den Index der Elemente, die miteinander verglichen und ggfs. vertauscht werden, wenn sie kleiner/größer als das Pivot sind.
        int leftPointer = fromIndex;
        int rightPointer = toIndex;
 
        // Partitioniere, so lange wie sich die Pointer nicht in die Quere kommen
        while (leftPointer < rightPointer)
        {
            // Verschiebe leftPointer so lange, bis ein Element gefunden wird, was größer als das Pivot ist
            // (oder wie sich die Pointer nicht überschneiden)
            while (arrayToSort[leftPointer] <= pivot && leftPointer < rightPointer)
            {
                leftPointer++;
            }
 
            // Verschiebe rightPointer so lange, bis ein Element gefunden wird, was größer als das Pivot ist
            // (oder wie sich die Pointer nicht überschneiden)
            while (arrayToSort[rightPointer] >= pivot && leftPointer < rightPointer)
            {
                rightPointer--;
            }
 
            // Vertausche die Elemente am Index von leftPointer und rightPointer
            int swapVar = arrayToSort[leftPointer];
            arrayToSort[leftPointer] = arrayToSort[rightPointer];
            arrayToSort[rightPointer] = swapVar;
        }
 
        // Vertausche die Elemente am Array-Index von leftPointer und toIndex
        int swapVar = arrayToSort[leftPointer];
        arrayToSort[leftPointer] = arrayToSort[toIndex];
        arrayToSort[toIndex] = swapVar;
 
        // QuickSort für die linke Seite vom Pivot-Element
        this.makeQuickSort(arrayToSort, fromIndex, leftPointer - 1);
 
        // QuickSort für die rechte Seite vom Pivot-Element
        this.makeQuickSort(arrayToSort, leftPointer + 1, toIndex);
    }
 
    // Konstruktor
    public QuickSort()
    {
        System.out.print("Vorher: ");
        this.OutputOfIntArray(myArray);
 
        long startZeit = System.nanoTime();
 
        // this.OutputOfIntArray(this.generateIntegerArrayOfSize(1000, 100));
        this.makeQuickSort(myArray, 0, myArray.length - 1);
 
        long endZeit = System.nanoTime();
 
        System.out.print("Nachher: ");
        this.OutputOfIntArray(myArray);
 
        System.out.println("Ich habe " + (endZeit - startZeit) + " ns gebraucht.");
    }
 
    public static void main(String[] args) 
    {
        // Instanziere aus den statischem Programm ein echtes Objekt
        // damit nicht alle Methoden und Variablen static sein müssen.
        program = new QuickSort();
    }
}

Ausgabe

Vorher: 22;6;2;4;10;3;9;7;5;8;1
Nachher: 1;2;3;4;5;6;7;8;9;10;22
Ich habe 7200 ns gebraucht.

Komplexität: O-Notation (Ordnung)

Der Quick-Sort hat im Average-Case die Komplexität O(n* log(n)) und im Worst-Case die Komplexität O(n²).

Algorithmen und Datenstrukutren: Binäre Suche vs. lineare Suche in JAVA

Der Algorithmus

Die binäre Suche funktioniert nur auf einem bereits sortiertem Datenbestand, daher wird die Zeit für das Sortieren des Arrays „myArray“ mit Merge-Sort auf die Such-Zeit addiert. Da die 11 Elemente im Beispiel-Array sehr wenige sind, sind die Zeiten in ms wenig repräsentativ.

package AlgoDat;
 
public class SearchAlgorithm {
    // Zu durchsuchendes Array
    private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
     
    // Hält die Klasse als instanziertes Objekt
    @SuppressWarnings("unused")
    private static SearchAlgorithm program;
 
    public int linearSearch(int[] array, int contentToSearchFor)
    {
        for (int i = 0; i < array.length; i++)
        {
            if (array[i] == contentToSearchFor)
            {
                return i;
            }
        }
 
        return -1;
    }
 
    public int binarySearch(int[] myArray, int contentToSearchFor)
    {
        // Start conditions
        int lowIndex = 0;
        int highIndex = myArray.length - 1;
 
        while (lowIndex <= highIndex)
        {
            int middlePosition = (lowIndex + highIndex) / 2;
            int middleContent = myArray[middlePosition];
 
            if (contentToSearchFor == middleContent) 
            {
                return middlePosition;
            }
 
            // Halbieren der Suchelemente
            if (contentToSearchFor < middleContent)
            {
                highIndex = middlePosition - 1;
            }
            else
            {
                lowIndex = middlePosition + 1;
            }
        }
 
        // Außerhalb der While-Schleife wissen wir, dass wir
        // das Element nicht gefunden haben :-(
        return -1;
    }
 
    // Konstruktor
    public SearchAlgorithm()
    {
        int arrayContent = -1;
        long startTime = 0;
        long endTime = 0;
        int index = -1;
        long passedTime = 0;
 
        System.out.println("Lineare Suche");
        System.out.println("=============");
        // Not found
        arrayContent = 23;
        startTime = System.nanoTime();
        index = linearSearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' wurde nicht gefunden in myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = endTime - startTime;
        System.out.println("Lineare Suche not found: " + passedTime + " ms.");
         
        // Best case
        arrayContent = 22;
        startTime =  System.nanoTime();
        index = linearSearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = endTime - startTime;
        System.out.println("Lineare Suche Best-Case: " + passedTime + " ms.");
 
        // Average case
        arrayContent = 3;
        startTime =  System.nanoTime();
        index = linearSearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = endTime - startTime;
        System.out.println("Lineare Suche Average-Case: " + passedTime + " ms.");
 
        // Worst case
        arrayContent = 1;
        startTime =  System.nanoTime();
        index = linearSearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = endTime - startTime;
        System.out.println("Lineare Suche Worst-Case: " + passedTime + " ms.");
 
        System.out.println("Binäre Suche");
        System.out.println("============");
 
        /*********************************************/
        /* die binäre Suche benötigt ein sortiertes  */
        /* Array, damit sie funktioniert.            */
        /*********************************************/
        startTime = System.nanoTime();
        this.mergeSort(myArray);
        endTime =  System.nanoTime();
        long passedSortTime = endTime - startTime;
 
        // Not found
        arrayContent = 23;
        startTime = System.nanoTime();
        index = binarySearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' wurde nicht gefunden in myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = passedSortTime + (endTime - startTime);
        System.out.println("Binäre Suche not found: " + passedTime + " ms.");
         
        // Best case
        arrayContent = 22;
        startTime =  System.nanoTime();
        index = binarySearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = passedSortTime + (endTime - startTime);
        System.out.println("Binäre Suche erstes Element: " + passedTime + " ms.");
 
        // Average case
        arrayContent = 3;
        startTime =  System.nanoTime();
        index = binarySearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = passedSortTime + (endTime - startTime);
        System.out.println("Binäre Suche mittleres Element: " + passedTime + " ms.");
 
        // Worst case
        arrayContent = 1;
        startTime =  System.nanoTime();
        index = binarySearch(myArray, arrayContent);
        System.out.print("Der Array-Element mit dem Inhalt '" + arrayContent + "' befindet sich am Index " + index + " von myArray[]. ");
        endTime =  System.nanoTime();
        passedTime = passedSortTime + (endTime - startTime);
        System.out.println("Binäre Suche letztes Element: " + passedTime + " ms.");
    }
 
    public static void main(String[] args) 
    {
        // Instanziere aus den statischem Programm ein echtes Objekt
        // damit nicht alle Methoden und Variablen static sein müssen.
        program = new SearchAlgorithm();
    }
 
    /**************/
    /* MERGE SORT */
    /**************/
 
    public void mergeSort(int myArray[])
    {
        // Abbruchbedingung der Rekursion im Sinne von Teile-und-Herrsche-Algorithmen
        if (myArray.length == 1) return;
 
        // weist bei ungeraden Zahlen eine abgerundete Ganzzahl zu
        int indexHaelfte = myArray.length / 2;
 
        int[] linkeHaelfte = new int[indexHaelfte];
 
        // Die abgerundete Ganzzahl kann von der Länge abgezogen werden
        // um die Größe des rechten Arrays zu erhalten.
        int[] rechteHaelfte = new int[myArray.length - indexHaelfte];
 
        // Befülle die linke Hälfte 
        for (int i = 0; i < indexHaelfte; i++)
        {
            linkeHaelfte[i] = myArray[i];
        }
 
        // Befülle die rechte Hälfte 
        for (int i = indexHaelfte; i < myArray.length; i++)
        {
            rechteHaelfte[i - indexHaelfte] = myArray[i];
        }
 
        // Hier ist der rekursive Aufruf, indem die beiden Hälften an
        // die mergeSort-Methode selbst übergeben wird.
        this.mergeSort(linkeHaelfte);
        this.mergeSort(rechteHaelfte);
 
        // Hier werden die beiden Arrays wieder kombiniert (geMerged)
        this.merge(myArray, linkeHaelfte, rechteHaelfte);
    }
 
    private void merge(int[] mergeArray, int[] linkeHaelfte, int[] rechteHaelfte)
    {
        int iteratorLinks = 0, iteratorRechts = 0, iteratorMergeArray = 0;
 
        // Da die linke und reche Hälfte bereits sortiert sind, funktioniert die Zuweisung
        // in ein neues Array mit einer einzigen Schleife der Komplexität/Ordnung O(n).
        while (iteratorLinks < linkeHaelfte.length && iteratorRechts < rechteHaelfte.length)
        {
            if (linkeHaelfte[iteratorLinks] <= rechteHaelfte[iteratorRechts])
            {
                mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
                iteratorLinks++;
            }
            else
            {
                mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
                iteratorRechts++;
            }
 
            iteratorMergeArray++;
        }
 
        // Wenn noch Elemente in der linken Hälfte waren, die nicht verglichen wurden,
        // werden diese dem Merged Array hinzugefügt
        while (iteratorLinks < linkeHaelfte.length)
        {
            mergeArray[iteratorMergeArray] = linkeHaelfte[iteratorLinks];
            iteratorLinks++;
            iteratorMergeArray++;
        }
 
        // Wenn noch Elemente in der rechten Array-Hälfte waren, die nicht verglichen wurden,
        // werden diese dem Merged Array hinzugefügt
        while (iteratorRechts < rechteHaelfte.length)
        {
            mergeArray[iteratorMergeArray] = rechteHaelfte[iteratorRechts];
            iteratorRechts++;
            iteratorMergeArray++;
        }
    }
}

Ausgabe

Lineare Suche
=============
Der Array-Element mit dem Inhalt '23' wurde nicht gefunden in myArray[]. Lineare Suche not found: 20969800 ms.
Der Array-Element mit dem Inhalt '22' befindet sich am Index 0 von myArray[]. Lineare Suche Best-Case: 9613200 ms.
Der Array-Element mit dem Inhalt '3' befindet sich am Index 5 von myArray[]. Lineare Suche Average-Case: 337400 ms.
Der Array-Element mit dem Inhalt '1' befindet sich am Index 10 von myArray[]. Lineare Suche Worst-Case: 270200 ms.
 
Binäre Suche
============
Der Array-Element mit dem Inhalt '23' wurde nicht gefunden in myArray[]. Binäre Suche not found: 206800 ms.
Der Array-Element mit dem Inhalt '22' befindet sich am Index 10 von myArray[]. Binäre Suche erstes Element: 271400 ms.
Der Array-Element mit dem Inhalt '3' befindet sich am Index 2 von myArray[]. Binäre Suche mittleres Element: 306700 ms.
Der Array-Element mit dem Inhalt '1' befindet sich am Index 0 von myArray[]. Binäre Suche letztes Element: 302800 ms.

Komplexität: O-Notation (Ordnung)

Die Komplexität der binären Suche wird mit

beschrieben, wobei die Komplexität des vorangegangenen Merge-Sort-Algorithmus mitgerechnet werden muss, da die binäre Suche nur auf einem binären Datenbestand funktioniert. Somit ergibt sich

, wobei die additiven Bestandteile log(n) wegfallen. Somit ergibt sich im vorliegenden Falle die Komplexität O(n*log(n)) wegen der vorangegangen Sortierung. Ist diese nicht notwendig bleibt es bei der O-Notation O(log(n)).