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)).

Algorithmen und Datenstrukturen: O-Notation / Komplexität der rekursiven Fakultät

Der Algorithmus

Bei der rekursiven Fakultät handelt es sich um einen rekursiven Funktionsaufruf:

package AlgoDat;
 
public class RekursiveFakultaet {
    // Zu sortierendes Array
     
    // Hält die Klasse als instanziertes Objekt
    @SuppressWarnings("unused")
    private static RekursiveFakultaet program;
 
    public long berechneFakultaet(int teilFakultaet)
    {
        // Abbruchbedingung der Rekursion wenn 1 erreicht ist
        if (teilFakultaet == 1) return 1;
 
        // Multipliziere rekursiv f(n) = n * f(n - 1) bis 1
        return teilFakultaet * berechneFakultaet(teilFakultaet - 1);
    }
 
    // Konstruktor
    public RekursiveFakultaet()
    {
        System.out.println(this.berechneFakultaet(25) + "");        
    }
 
    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 RekursiveFakultaet();
    }
}

Ausgabe

7034535277573963776

Komplexität: O-Notation (Ordnung)

Der rekursive Aufruf dieser Art kann als primitiv rekursiven Klasse gezählt werden und besitzt die lineare Komplexität / O-Notation:

Algorithmen und Datenstrukturen: Der Merge Sort in Java

Der Algorithmus

Der MergeSort-Algorithmus ist ein stabiler Sortieralgorithmus nach dem Teile-und-Herrsche-Prinzip. Im ersten Teil wird das Array rekursiv so lange halbiert, bis in jeder Liste nur noch 1 Element vorhanden ist. Bei einer Liste mit einem Element geht man davon aus, dass die Liste automatisch als sortiert gilt. Danach können alle nachfolgenden Operationen von zwei sortierten Listen ausgehen, wodurch weniger Operationen beim Zusammenführen ausreichen um ein neues sortiertes Array zu erhalten.

Im zweiten Teil werden die bereits sortierten Listenhälften verglichen und mit der Komplexität O(n) je rekursiver Iteration verglichen und zusammengeführt (siehe den nachfolgenden JAVA Code).

package AlgoDat;

public class MergeSort {
    // 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 MergeSort 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();
        }
    }

    public void mergeSort(int myArray[])
    {
        // zunächst wird das Array ab der Hälfte in zwei
        // Arrays links und rechts geteilt, das passiert
        // rekursiv ... und zwar so lange bis jedes Element
        // für sich nur noch 1x vorhanden ist (Teile-Herrsche-Prinzip).
        // Das Teilen ist damit erledigt und nun sollte da
        // Problem dadurch beherrschbarer werden -> nun 
        // werden die Einzelelemente wieder in Arrays sortiert. 
        // Die Abbruchbedingung der Rekursion ist, wenn die Liste 
        // nur noch ein einziges Element hat, wobei die Liste bei
        // einem einzigem Element als sortiert gilt.
        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)
    {
        System.out.print("Vergleiche linke Hälfte: ");
        this.OutputOfIntArray(linkeHaelfte);
        System.out.print("mit rechter Hälfte ");
        this.OutputOfIntArray(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++;
        }
    }

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

        // Wir lagern alles weitere in eine eigene Methode aus, 
        // da MergeSort ein rekursiver Algorithmus ist, dessen 
        // Funktion aufgerufen werden muss und beeginnen mit dem 
        // unsortierten Array
        this.mergeSort(myArray);

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

    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 MergeSort();
    }
}

Ausgabe

Vorher: 22;6;2;4;10;3;9;7;5;8;1
Vergleiche linke Hälfte: 22
mit rechter Hälfte 6
Vergleiche linke Hälfte: 4
mit rechter Hälfte 10
Vergleiche linke Hälfte: 2
mit rechter Hälfte 4;10
Vergleiche linke Hälfte: 6;22
mit rechter Hälfte 2;4;10
Vergleiche linke Hälfte: 9
mit rechter Hälfte 7
Vergleiche linke Hälfte: 3
mit rechter Hälfte 7;9
Vergleiche linke Hälfte: 8
mit rechter Hälfte 1
Vergleiche linke Hälfte: 5
mit rechter Hälfte 1;8
Vergleiche linke Hälfte: 3;7;9
mit rechter Hälfte 1;5;8
Vergleiche linke Hälfte: 2;4;6;10;22
mit rechter Hälfte 1;3;5;7;8;9
Nachher: 1;2;3;4;5;6;7;8;9;10;22

Komplexität: O-Notation (Ordnung)

Der MergeSort besteht aus 3 Teilen, die sich zu der Gesamtkomplexität zusammensetzen.

Teil 1: (Rekursives) Teilen

Wenn wir ein Array der Größe n in zwei Hälften teilen, benötigen wir

Schritte. Hierbei handelt es sich um den Logarithmus dualis, also den Logarithmus zur Basis 2 (wessen Basis für die 2 Hälften spricht, in die aufgeteilt wird). Dies liegt also daran, dass wir die Liste in jeder Rekursionsebene halbieren. Wir fragen hier also mit welcher Zahl man 2 potenzieren muss um n zu erhalten.

Wenn wir in dem unsortierten Array 11 Elemente haben, würden wir also fragen, mit welcher Zahl wir 2 potenzieren müssen um 11 zu erhalten. Den Exponenten den wir hier erhalten wäre 4:

Wir runden die Kommazahl immer auf die nächste volle Zahl auf, da wir keine halben Schritte machen können. Die Zahl 4 entspricht hier auch der Rekursionstiefe, die benötigt wird bis der aktuelle Rekursions-Heap nur noch aus einem Element bekommt, was zu Abbruch der Rekursion führt.

Der erste Teil besitzt somit die Ordnung:

Teil 2 und 3: Sortieren und Mergen

Der Schritt des Zusammenführens (des Mergens) beider Liste ist mit der Sortierung kombiniert. Hier wird vorausgesetzt dass bereits sortierte Listenhälften vorliegen, da man zwei bereits sortierte Arrays mit der Komplexität n vergleichen kann. Beim Zusammenführen der sortierten Teillisten benötigen wir

Zeit. Dieser Schritt ist linear abhängig von der Gesamtanzahl der Elemente.

Gesamt-Komplexität

Somit ergibt sich die Gesamtkomplexität:

im Worst-, Normal- und Best-Case.

Algorithmen und Datenstrukturen: Der Bubble Sort in Java

Der Algorithmus

Beim „Bubble Sort“ markiert die äußere Schleife das erste Element des noch unsortierten Bereichs, während die innere Schleife ab diesem Element immer bis zum Ende des Arrays ein Element zum Vergleich rauspickt. Ist ein Element kleiner/größer (je nachdem wie der Vergleichsoperator „gedreht“ ist) wird getauscht.

Dies führt am Ende zu der Sortierung des Arrays. Im Gegesatz zum Selection Sort, wo nur das Minimum getauscht wird, wird beim Bubble Sort immer getauscht.

package AlgoDat;

public class BubbleSort {
    // 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 BubbleSort 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 BubbleSort()
    {
        System.out.print("Vorher: ");
        this.OutputOfIntArray(myArray);

        // Äußere Schleife: Laufe das zu sortierende Array von Anfang bis Ende durch (Komplexität: n)
        for (int idxSortierterBereich = 0; idxSortierterBereich < myArray.length - 1 ; idxSortierterBereich++)
        {
            // Innere Schleife: Laufe das Array ab dem Index der äußeren Schleife bis Ende durch (Komplexität: n / 2)
            for (int idxUnsortierterBereich = idxSortierterBereich + 1; idxUnsortierterBereich < myArray.length; idxUnsortierterBereich++)
            {
                // Tausche die Array-Inhalte an den Indizes der inneren und äußeren Schleife
                // wenn diese kleiner/größer sind. Anmerkung: Ein Drehen von < zu > ändert die Sortierreihenfolge
                if (myArray[idxUnsortierterBereich] < myArray[idxSortierterBereich])
                {
                    // Beim Bubble Sort wird im Gegensatz zum Selection Sort immer getauscht.
                    // Beim Selection Sort wird nur das gefundene Minimum getauscht. 
                    // Dieser Code tauscht das Element am Index der äußeren Schleife                
                    // mit dem Element am Index der inneren Schleife
                    int swapVar = myArray[idxUnsortierterBereich];
                    myArray[idxUnsortierterBereich] = myArray[idxSortierterBereich];
                    myArray[idxSortierterBereich] = swapVar;

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

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

    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 BubbleSort();
    }
}

Ausgabe

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

Komplexität: O-Notation (Ordnung)

O(T(n)) = O(n²)

Algorithmen und Datenstrukturen: Der Selection Sort in Java

Der Algorithmus

package AlgoDat;

public class SelectionSort {
    // 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 SelectionSort 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 SelectionSort()
    {
        System.out.print("Vorher: ");
        this.OutputOfIntArray(myArray);

        // Laufe das zu sortierende Array von Anfang bis Ende durch
        for (int idxSortierterBereich = 0; idxSortierterBereich < myArray.length - 1 ; idxSortierterBereich++)
        {
            // Starte an der Index-Position der äußersten Schleife - davor ist schon alles sortiert
            int indexPivotElement = idxSortierterBereich;

            for (int idxUnsortierterBereich = idxSortierterBereich + 1; idxUnsortierterBereich < myArray.length; idxUnsortierterBereich++)
            {
                // ... und merke dir das kleinste Element
                if (myArray[indexPivotElement] > myArray[idxUnsortierterBereich])
                {
                    indexPivotElement = idxUnsortierterBereich;
                }
            }

            // Dieser Code tauscht das neu gefundene Minimum mit dem Element am aktuellen Index der äußeren Schleife                
            int swapVar = myArray[indexPivotElement];
            myArray[indexPivotElement] = myArray[idxSortierterBereich];
            myArray[idxSortierterBereich] = swapVar;

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

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

    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 SelectionSort();
    }
}

Ausgabe

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

Komplexität: O-Notation (Ordnung)

Zwei verschaltete Schleifen.
Die äußere Schleife läuft von 1 bis n;
Die innere Schleife läuft vom Element der äußeren Schleife bis Schluss -> also n/2, da der Bereich immer kleiner wird.

O(T(n)) = O(n²)

by Björn Karpenstein