Schlagwort-Archive: sortieren

Algorithmen und Datenstrukturen, Java, Programmierung

Algorithmen und Datenstrukturen: Der optimierte Bubble Sort in Java

Schreibe einen Kommentar

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, Allgemein

Algorithmen und Datenstrukturen: Der Selection Sort in Java

Schreibe einen Kommentar

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

Algorithmen und Datenstrukturen, Java, Programmierung

Algorithmen und Datenstrukturen: Der Insertion Sort in Java

Schreibe einen Kommentar

Der Algorithmus

Markant sind die zwei verschachtelten Schleifen, wobei die innere Schleife meistens eine While-Schleife mit 2 Bedingungen ist. Ein Index, welcher die Position der Trennung vom sortierten (links) und vom unsortierten (rechts) Bereich präsentiert, wird runtergezählt und das Array-Element an der Index-Position entspricht nach Ende der Schleife der Array-Position, mit der ein gemerktes Element getauscht werden kann. Während der sortierte Bereich (immer links) mit dem ersten Element des unsortierten Bereichs (immer rechts), welches sich gemerkt wird, verglichen wird, werden alle Elemente bis zu diesem Punkt um eins nach rechts gerückt. Dadurch existiert die zu tauschende Position nach diesem Schritt zwei Mal und wird durch das gemerkte Element ausgetauscht.

Die zweite Bedingung der inneren While-Schleife verhindert, das der runterzählende Index negativ wird. 

package AlgoDat;

class InsertionSort {
    // Zu sortierendes Array
    private int myArray[] = {22, 6, 2, 4, 10, 3, 9, 7, 5, 8, 1};
    
    // Hält die Klasse InsertionSort als instanziertes Objekt
    @SuppressWarnings("unused")
    private static InsertionSort 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 InsertionSort()
    {
        this.OutputOfIntArray(myArray);

        // Bei 1 beginnen, da das Element mit dem Index 0 bereits als sortiert gilt 
        for (int idxSortierterBereich = 1; idxSortierterBereich < myArray.length; idxSortierterBereich++)
        {
            // Merke dir das erste Element vom unsortierten Bereich
            int swapVar = myArray[idxSortierterBereich];
            System.out.println("Gemerkt vor dem Aufrücken: " + swapVar);

            // Das erste unsortierte Element auf der rechten Seite wird in den bereits sortierten Bereich 
            // auf der linken Seite eingefügt, womit der unsortierte Bereich immer weiter nach rechts rückt
            // und dann verschwindet.
            int idxUnsortierterBereich = idxSortierterBereich; 
            System.out.println("Der unsortierte Bereich beginnt bei Index: " + idxUnsortierterBereich);

            // Laufe im Array von rechts nach links, so lange wie vorige Element noch größer wie 
            // das erste Element vom unsortierten Bereich ist und der Bereich nicht negativ wird
            while (idxUnsortierterBereich > 0 && myArray[idxUnsortierterBereich - 1] > swapVar)
            {
                // Alles eins nach rechts im Array rücken bis zum bereits sortierten Bereich
                myArray[idxUnsortierterBereich] = myArray[idxUnsortierterBereich - 1] ;
                idxUnsortierterBereich--;

                System.out.print("Nach rechts aufrücken: ");
                this.OutputOfIntArray(myArray);
            }

            System.out.println("Tausche Stelle " + (idxUnsortierterBereich + 1) + " (" + myArray[idxUnsortierterBereich] + 
            ") mit gemerkter Stelle " + (idxSortierterBereich + 1) + " (" + swapVar + ")");

            myArray[idxUnsortierterBereich] = swapVar;

            System.out.print("Getauscht: ");
            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 InsertionSort();
    }
}

Ausgabe

22;6;2;4;10;3;9;7;5;8;1
Gemerkt vor dem Aufrücken: 6
Der unsortierte Bereich beginnt bei Index: 1
Nach rechts aufrücken: 22;22;2;4;10;3;9;7;5;8;1
Tausche Stelle 1 (22) mit gemerkter Stelle 2 (6)
Getauscht: 6;22;2;4;10;3;9;7;5;8;1
Gemerkt vor dem Aufrücken: 2
Der unsortierte Bereich beginnt bei Index: 2
Nach rechts aufrücken: 6;22;22;4;10;3;9;7;5;8;1
Nach rechts aufrücken: 6;6;22;4;10;3;9;7;5;8;1
Tausche Stelle 1 (6) mit gemerkter Stelle 3 (2)
Getauscht: 2;6;22;4;10;3;9;7;5;8;1
Gemerkt vor dem Aufrücken: 4
Der unsortierte Bereich beginnt bei Index: 3
Nach rechts aufrücken: 2;6;22;22;10;3;9;7;5;8;1
Nach rechts aufrücken: 2;6;6;22;10;3;9;7;5;8;1
Tausche Stelle 2 (6) mit gemerkter Stelle 4 (4)
Getauscht: 2;4;6;22;10;3;9;7;5;8;1
Gemerkt vor dem Aufrücken: 10
Der unsortierte Bereich beginnt bei Index: 4
Nach rechts aufrücken: 2;4;6;22;22;3;9;7;5;8;1
Tausche Stelle 4 (22) mit gemerkter Stelle 5 (10)
Getauscht: 2;4;6;10;22;3;9;7;5;8;1
Gemerkt vor dem Aufrücken: 3
Der unsortierte Bereich beginnt bei Index: 5
Nach rechts aufrücken: 2;4;6;10;22;22;9;7;5;8;1
Nach rechts aufrücken: 2;4;6;10;10;22;9;7;5;8;1
Nach rechts aufrücken: 2;4;6;6;10;22;9;7;5;8;1
Nach rechts aufrücken: 2;4;4;6;10;22;9;7;5;8;1
Tausche Stelle 2 (4) mit gemerkter Stelle 6 (3)
Getauscht: 2;3;4;6;10;22;9;7;5;8;1
Gemerkt vor dem Aufrücken: 9
Der unsortierte Bereich beginnt bei Index: 6
Nach rechts aufrücken: 2;3;4;6;10;22;22;7;5;8;1
Nach rechts aufrücken: 2;3;4;6;10;10;22;7;5;8;1
Tausche Stelle 5 (10) mit gemerkter Stelle 7 (9)
Getauscht: 2;3;4;6;9;10;22;7;5;8;1
Gemerkt vor dem Aufrücken: 7
Der unsortierte Bereich beginnt bei Index: 7
Nach rechts aufrücken: 2;3;4;6;9;10;22;22;5;8;1
Nach rechts aufrücken: 2;3;4;6;9;10;10;22;5;8;1
Nach rechts aufrücken: 2;3;4;6;9;9;10;22;5;8;1
Tausche Stelle 5 (9) mit gemerkter Stelle 8 (7)
Getauscht: 2;3;4;6;7;9;10;22;5;8;1
Gemerkt vor dem Aufrücken: 5
Der unsortierte Bereich beginnt bei Index: 8
Nach rechts aufrücken: 2;3;4;6;7;9;10;22;22;8;1
Nach rechts aufrücken: 2;3;4;6;7;9;10;10;22;8;1
Nach rechts aufrücken: 2;3;4;6;7;9;9;10;22;8;1
Nach rechts aufrücken: 2;3;4;6;7;7;9;10;22;8;1
Nach rechts aufrücken: 2;3;4;6;6;7;9;10;22;8;1
Tausche Stelle 4 (6) mit gemerkter Stelle 9 (5)
Getauscht: 2;3;4;5;6;7;9;10;22;8;1
Gemerkt vor dem Aufrücken: 8
Der unsortierte Bereich beginnt bei Index: 9
Nach rechts aufrücken: 2;3;4;5;6;7;9;10;22;22;1
Nach rechts aufrücken: 2;3;4;5;6;7;9;10;10;22;1
Nach rechts aufrücken: 2;3;4;5;6;7;9;9;10;22;1
Tausche Stelle 7 (9) mit gemerkter Stelle 10 (8)
Getauscht: 2;3;4;5;6;7;8;9;10;22;1
Gemerkt vor dem Aufrücken: 1
Der unsortierte Bereich beginnt bei Index: 10
Nach rechts aufrücken: 2;3;4;5;6;7;8;9;10;22;22
Nach rechts aufrücken: 2;3;4;5;6;7;8;9;10;10;22
Nach rechts aufrücken: 2;3;4;5;6;7;8;9;9;10;22
Nach rechts aufrücken: 2;3;4;5;6;7;8;8;9;10;22
Nach rechts aufrücken: 2;3;4;5;6;7;7;8;9;10;22
Nach rechts aufrücken: 2;3;4;5;6;6;7;8;9;10;22
Nach rechts aufrücken: 2;3;4;5;5;6;7;8;9;10;22
Nach rechts aufrücken: 2;3;4;4;5;6;7;8;9;10;22
Nach rechts aufrücken: 2;3;3;4;5;6;7;8;9;10;22
Nach rechts aufrücken: 2;2;3;4;5;6;7;8;9;10;22
Tausche Stelle 1 (2) mit gemerkter Stelle 11 (1)
Getauscht: 1;2;3;4;5;6;7;8;9;10;22

Komplexität: O-Notation (Ordnung)

O(T(n)) = O(n^2/2+n/2-n) = O(n^2/2) = O (n^2)

Die äußere Schleife läuft von 1 bis n-1, während die innere While-Schleife vom ersten Element des unsortierten Bereichs bis zu der Stelle der richtige Einfügeposition läuft.

Äußere Schleife: Iteriert n-1 mal.
Innere Schleife: Iteriert 1x für Element 1, 2x für Element 2, 3x für Element 3, … n mal für Element n, was zu einer Laufzeit von

führt. Daraus folgt:

Additive Bestandteile, Faktoren und Konstanten fallen bei der Bestimmung der Ordnung weg, daher ist die Ordnung O(n²). Die Domäne ist der dominante Teil der Ordnung – sie ist n² .