Schlagwort-Archive: Sortieralgorithmus

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

Algorithmen und Datenstrukturen: Der Insertion Sort in Java

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