Archiv der Kategorie: Java

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

Android&PHP Backend: Netzwerkkommunikation, Authentifizierung und Login

Aufgabenstellung

Es wird eine Möglichkeit gesucht eine Android App mit einen PHP Backend kommunizieren zu lassen

Intention

PHP mit MySQL Server erhält man oft schon mit billigem Webspace. Ein weiterer Vorteil eines fertigen Webpacks/Webspace ist, dass es nicht notwendig wird sich um eine Backupstrategie zu kümmern. In den meisten Fällen (SLAs und AGBs des Providers studieren) liegt dieses Problem in den Händen des Providers. Er kümmert sich auch um die Sicherheit des Servers. Bei Hackerattacken ist man nicht in der Verantwortung den Server zu härten und zu schützen. Daher kann der Provider auch keine Schadensersatzansprüche gegen den Kunden geltend machen, wenn ein Server gekapert wird und z.B. mit der Installation eines Botnetzes die Leistungsfähigkeit des Rechenzentrums beeinträchtigt ist.

Ansatz

  • Implementierung eines möglichst einfachen Authentifierungsmechanismus in PHP mit MySQL-Anbindung
  • Wegkapseln der Serviceaufrufe
  • Asynchrone Verarbeitung der JSON Aufrufe per Java Thread
    • Reaktion in der MainActivity beim Erhalten des Service-Ergebnisses für UI Manipulationen

Der häufigste Ansatz, den man in Tutorials findet, ist die Kommunikation über JSON, einem kompakten Datenformat in für Mensch und Maschine einfach lesbarer Textform zum Zweck des Datenaustauschs zwischen Anwendungen.

Lösung

BjoernServiceCaller.java – Klasse für weggekapselte Service aufrufe mit CallBack-Funktionalität über onLoginResult

package com.caprisoft.contactupload.services;

import java.io.BufferedReader;
import java.io.InputStreamReader;

import org.apache.http.HttpResponse;
import org.apache.http.client.HttpClient;
import org.apache.http.client.methods.HttpPost;
import org.apache.http.entity.StringEntity;
import org.apache.http.impl.client.DefaultHttpClient;
import org.apache.http.message.BasicHeader;
import org.apache.http.params.HttpConnectionParams;
import org.apache.http.protocol.HTTP;
import org.json.JSONArray;
import org.json.JSONObject;
import org.json.JSONTokener;

import com.caprisoft.contactupload.MainActivity;

import android.content.Context;
import android.os.Looper;
import android.util.Log;
import android.widget.Toast;


public class BjoernsServiceCaller 
{
	
	final String authenticationURL = "authenticationservice.php";
	private static BjoernsServiceCaller instance = null;
	private BjoernsServiceCaller() 	{}
	

    /**
     * Statische Methode, liefert die einzige Instanz dieser
     * Klasse zurück
     */
    public static BjoernsServiceCaller getInstance() 
    {
        if (instance == null) 
        {
            instance = new BjoernsServiceCaller();
        }
        return instance;
    }
	
	
	public void loginUser(final MainActivity ctx, 
                                    final String email, final String password) 
	{
        Thread t = new Thread()
        {
	        public void run() 
	        {
                        //For Preparing Message Pool for the child Thread
		        Looper.prepare(); 
				
		        HttpClient client = new DefaultHttpClient();
                         //Timeout Limit
		        HttpConnectionParams
                               .setConnectionTimeout(client.getParams(), 10000);
		        HttpResponse response;
		        JSONObject json = new JSONObject();
		        try
		        {
		            HttpPost post = new HttpPost(authenticationURL);
		            json.put("email", email);
		            json.put("password", password);
		            StringEntity se = new StringEntity( json.toString());  
		            se.setContentType(new BasicHeader(HTTP.CONTENT_TYPE,
                                          application/json"));
		            post.setEntity(se);
		            response = client.execute(post);
		            /*Checking response */
		            if(response!=null)
		            {
		                BufferedReader reader = new BufferedReader
                                (
                                    new InputStreamReader
                                    (
                                       response.getEntity().getContent(), "UTF-8"
                                    )
                                );
		                String derText = reader.readLine();
                                // CallBack aufruf in MainActivity
		                ctx.onLoginResult(derText);
		            }
		
		        }
		        catch(Exception e)
		        {
		            e.printStackTrace();
		        }
		        Looper.loop(); //Loop in the message queue
	        }
        };
        t.start();          
    }
}

authenticationservice.php – Das PHP Backend, was die Datenbankabfragen macht und auf jedem Billigwebspace läuft

<?php  
    include("configuration/database.php");
	$json = file_get_contents('php://input');
	$obj = json_decode($json);
	$result2=mysql_query("SELECT id, activationcode FROM users ".
                                      "WHERE email='".$obj->{'email'}."' AND ".
                                      "password='".$obj->{'password'}."'") 
                                       or die(mysql_error());
	
	$user="nouser";
	while ($row = mysql_fetch_array($result2, MYSQL_NUM)) {
	   $user=$row[0];
	   $activationcode=$row[1];
	}	
    
    $posts = array(1);
    
    if($user!="nouser")
    {
    	if($activationcode=="activated")
    	{
    		session_start();
    		session_register("userid");
    		$_SESSION["userid"] =$user;
    		header('Content-type: application/json');
    		echo "success";
    	}
    	else 
    	{
    	   $registrationcode=substr(md5($obj->{'email'}." ".$obj->{'password'}),6);
    	   mysql_query("UPDATE users SET activationcode='".$registrationcode.
           "' WHERE email='".$obj->{'email'}."'") or die(mysql_error());
    	   mail($obj->{'email'},"Registrationcode for contactupload.com",
            "Hello!<br><br>\n You or someone else has registered this email ".
            "address via mobile phone.<br><br>\nThe generated registrationcode is ".
            $registrationcode.".<br><br>\nPlease type this registrationcode in ".
            "the register section of the contact sync app.<br><br> .
            "\nWith best regards,<br>\ncontactupload.com");
    		echo "not activated";
    	}
    }
    else 
    {
        echo "not registered";
    } 
    mysql_close($con);
?>

MainActivity.java – Die Klasse präsentiert den Code der Benutzeroberfläche der Activity (VIEW)

package com.caprisoft.contactupload;

import com.caprisoft.contactupload.services.BjoernsServiceCaller;

import android.os.Bundle;
import android.app.Activity;
import android.util.Log;
import android.view.Menu;
import android.view.View;
import android.widget.EditText;
import android.widget.Toast;

public class MainActivity extends Activity {
	
	private EditText email = null;
	private EditText passwort = null;
	
	/** Called when the user selects the Send button */
	public void onClickLoginButton(View view) {
	    // Do something in response to button
		Log.d(this.getClass().toString(), "Login Button gedrückt!");
		BjoernsServiceCaller.
                getInstance().
                loginUser
                (
                    this, 
                    email.getText().toString(), 
                    passwort.getText().toString()
                );
	}
	
	/** Called when the user selects the Send button */
	public void onClickRegisterButton(View view) {
	    // Do something in response to button
		Log.d(this.getClass().toString(), "Register Button gedrückt!");
	}	
	
	public void onLoginResult(String text)
	{
		Toast.makeText(this, "HALLO: "+text, Toast.LENGTH_LONG).show();
	}

    @Override
    public void onCreate(Bundle savedInstanceState) {
        super.onCreate(savedInstanceState);
        setContentView(R.layout.activity_main);
        
        email = (EditText) findViewById(R.id.textUsername);
        passwort = (EditText) findViewById(R.id.textPassword);
    }

    @Override
    public boolean onCreateOptionsMenu(Menu menu) {
        getMenuInflater().inflate(R.menu.activity_main, menu);
        return true;
    }

    
}

Activity_main.xml – Das eigentliche Frontend

<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
    xmlns:tools="http://schemas.android.com/tools"
    android:orientation="vertical"
    android:layout_width="match_parent"
    android:layout_height="match_parent" >

    <TextView
        android:id="@+id/labelUsername"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:text="@string/labelUsername"
        android:textAppearance="?android:attr/textAppearanceLarge" />
    
  <EditText android:id="@+id/textUsername"
        android:layout_height="wrap_content"
        android:layout_width="match_parent"
        android:inputType="textNoSuggestions"
        android:hint="@string/hintUsername" />
  
   <TextView
        android:id="@+id/labelPassword"
        android:layout_width="wrap_content"
        android:layout_height="wrap_content"
        android:text="@string/labelPassword"
        android:textAppearance="?android:attr/textAppearanceLarge" />
      
   <EditText android:id="@+id/textPassword"
        android:layout_height="wrap_content"
        android:layout_width="match_parent"
        android:inputType="textPassword"
        android:hint="@string/hintPassword" />

   <Button
       android:id="@+id/buttonLogin"
       android:layout_width="match_parent"
       android:layout_height="wrap_content"
       android:onClick="onClickLoginButton"
       android:text="@string/buttonLogin" />

   <Button
       android:id="@+id/buttonRegister"
       android:layout_width="match_parent"
       android:layout_height="wrap_content"
       android:onClick="onClickRegisterButton"
       android:text="@string/buttonRegister" />
  
</LinearLayout>

AndroidManifest.xml – Permission für den Zugriff auf das Internet einrichten

<manifest xmlns:android="http://schemas.android.com/apk/res/android"
    package="com.caprisoft.contactupload"
    android:versionCode="1"
    android:versionName="1.0" >

    <uses-sdk
        android:minSdkVersion="8"
        android:targetSdkVersion="15" />
     <uses-permission android:name="android.permission.INTERNET" /> 
    <application
        android:icon="@drawable/ic_launcher"
        android:label="@string/app_name"
        android:theme="@style/AppTheme" >
        <activity
            android:name=".MainActivity"
            android:label="@string/title_activity_main" >
            <intent-filter>
                <action android:name="android.intent.action.MAIN" />

                <category android:name="android.intent.category.LAUNCHER" />
            </intent-filter>
        </activity>
    </application>
</manifest>

SAP und JAVA: Zugriff auf Funktionsbausteine / BAPIs mit dem Java Connector

Aufgabenstellung

Es soll auf Daten aus dem SAP System zugegriffen werden, ohne die Datenbank direkt anzusprechen.

Ansatz

Durch die Verwendung des Java-Connectors (JCo) werden Funktionsbausteine / BAPIs als SAP Schnittstellen verwendet. Die Funktionsbausteine können über die SAP GUI mit dem BAPI-Explorer gesucht und mit der TA 37 getestet werden. Der nachfolgende Artikel beschäftigt sich mit dem Aufruf von einem Java-Server. Der JCo kann im Market Place von SAP kostenlos heruntergeladen werden.

Lösung

Remote Function Call (techn. RPC)

Ein Remote Function Call (RFC) ist die SAP-Implementierung von Remote Procedure Calls (RPC). Über einen RFC lassen sich Funktionsbausteine, bzw. BAPI’s aufrufen.

Ein RFC verwendet die Kommunikationsregeln des CPI-C-Protokolls, welches auf TCP/IP oder LU 6.2 basiert. LU 6.2 war dabei das Kommunikationsprotokoll von R/2-Mainframe-Systemen und wurde bei R/3 durch den einheitlichen TCP/IP-Standard ersetzt.

RFC’s nehmen ausschließlich Call-By-Value-Parameter entgegen, da die Übergabe von Zeigern und Speicheradressen hier keinen Sinn macht. In einem fremden System würde die Speicheradresse auf einen Speicher-Bereich zeigen, in dem keine oder Daten von anderen Anwendungen vorhanden sind.

Funktionsweise des Java Connectors (JCo)

Der Java Connector unterstützt den Aufruf von RFC’s, bzw. BAPIs aus einer externen Java-Umgebung (SAP-inbound-call), sowie den Aufruf externer JAVA-Funktionalitäten aus ABAP-Programmen heraus (SAP-outbound-call). Für die letztgenannte Variante existiert im Example-Verzeichnis des JCo ein Beispiel, in dem ein JCo-Server implementiert wird. Der JCo-Server muss dem SAP-System über die Transaktion SM59 bekanntgemacht werden.

Bei einem SAP-Inbound-Call ist die Vorgehensweise die folgende:

1.) Anmeldung der Java-Applikation am R/3-System

JCO.Client Conection = JCO.createClient(Mandant,
                                        Username,
                                        Password,
                                        Language,
                                        Hostname,
                                        Systemnummer);

Connection.connect();

2.) Herunterladen des Repository für den Funktionsbaustein

IRepository rep = JCO.createRepository("MyRepository", Connection);
IFunctionTemplate template = rep.getFunctionTemplate("BAPI_NAME");
JCO.Function funktion = new JCO.Function(template);

3.) Holen einer Referenz auf die Übergabeparameter

JCO.ParameterList import = funktion.getImportParameterList();
JCO.ParameterList table = funktion.getTableParameterList();

4.) Befüllen des Bausteins

5.) Funktionsbaustein ausführen

Connection.execute(funktion);

6.) Hole Referenz auf Rückgabeparameter

JCO.ParameterList export = funktion.getExportParameterList();
JCO.ParameterList table = funktion.getTableParameterList();

7.) Auslesen des Bausteins

Es werden synchrone (sRFC), asynchrone (aRFC) und transaktionale Aufrufe (tRFC, qRFC), sowie Connection-Pooling unterstützt (auf JAVA- wie auf ABAP-Seite).

SAP lobt zwar die Plattformunabhängigkeit des Connectors, jedoch stößt man bei einfachem Kopieren des Bytecodes auf Probleme, da hier eine plattformabhängige Bibliotheksdatei gekapselt wird, die bei höheren Releases nicht mehr funktioniert. Unter Windows wird die Datei librfc32.dll und unter Linux die Datei librfccm.so gekapselt.

Durch die Kapselung der Datei ist es ohne weiteres möglich, Konnektoren für nicht unterstützte Programmiersprachen zu implementieren.

Ein Tutorial der Zeitschrift „Der Entwickler“, welches Online zur Verfügung steht, zeigt durch Verwendung dieser Bibliothek, wie man Delphi an SAP-Systeme andocken kann. Der Artikel trägt den Namen „Delphi goes SAP“. Da es für Delphi keine Konnektoren wie den Java Connector gibt, ist die Kapselung dieser Datei notwendig.

Parameter von Funktionsbausteinen

Da die meisten SAP-Anwendungen im ABAP-Stack implementiert worden, greift man mit dem JAVA Connector hauptsächlich auf remotefähige Funktionsbausteine zu. Diesen werden entweder ausgefüllte Tabellen, oder Import-Parameter zur Verarbeitung übergeben. Als Ausgabe liefert ein Funktionsbaustein Fehler-Parameter, Export-Parameter, neue Tabellen oder auch die übergebenen Tabellen mit neuen Werten zurück. Hierfür ist es notwendig den syntaktischen Aufbau von JCO-Syntax zu kennen.

Import-Parameter

Import-Parameter kann man sich wie einfache Übergabeparametern aus bekannten Programmiersprachen vorstellen. Ein Import-Parameter entspricht einem Feld, was einen Datentyp beinhaltet (Char, Integer, String, Double…). Es kann keine Array’s, Listen oder Tabellen entgegennehmen.

SAP kennzeichnet hauseigene Funktionsbausteine mit einem vorangehenden I für „Import“. Mit der Transaktion SE16 ist es möglich sich die notwendigen Import-Parameter anzusehen.

Nicht alle Import-Parameter sind erforderlich, es gibt auch optionale Parameter. Nicht jeder Funktionsbaustein hat Import-Parameter.

Der nachstehende Code zeigt, wie mit Hilfe des JAVA Connectors der Funktionsbaustein „CFX_API_USER_GETDETAIL“, der die Detaildaten eines cFolders-Benutzers zurückgibt befüllt wird:

public String gibListeVonUsern()
{
  IRepository repository = JCO.createRepository("MYRepository", client);
  IFunctionTemplate ftemplate = repository
 .getFunctionTemplate("CFX_API_USER_GETDETAIL");
  Function func = ftemplate.getFunction();

  JCO.ParameterList input = func.getImportParameterList();
  input.setValue("KARPBJ01", "I_USER_ID");

  // Funktion aufrufen
  client.execute(func);
  (...)
}

Export-Parameter

Nachdem die Funktion ausgeführt wurde, kann über die Export-Parameter iteriert werden um die Rückgabewerte auszulesen. Dazu hat die Klasse ParameterList die Methode getFieldCount(), welche die Anzahl der Rückgabeparameter zurückliefert. Die Methode getString(index) ermöglich über den inkrementellen Index die Iteration mit einer Schleife. Dadurch lassen sich alle Parameter dynamisch auslesen.

Nachfolgend wird aus der aufgerufenden Funktion über die Export-Parameterliste iteriert und das Ergebnis an den String „informationen“ angehangen.


public String gibListeVonUsern()
{
  (...) //Hier war der Funktionsaufruf

  JCO.ParameterList output = func.getExportParameterList();

  for (int i = 0; i < output.getFieldCount(); i++)
  {
    informationen = informationen + output.getString(i) + "\n";
  }
  return informationen;
}

Changing-Parameter

Im Gegensatz zu Import- und Export-Parametern funktionieren Changing-Parameter in beide Richtungen (bidirektional). Der Aufruf ist dabei Call-By-Reference-ähnlich, da sich nach dem Ausführen des Funktionsbausteins mit dem Befehl client.execute(func); der Wert im Feld ändern kann. Das Befüllen und auslesen funktioniert dabei wie bei den Import- und Export-Parametern.

Table-Parameter

Table-Parameter sind bidirektional. Die Referenz auf eine Tabelle kann geholt werden, bevor die Funktion ausgeführt wurde. Hat man die Referenz auf die Tabelle, so lässt sich diese folgendermaßen befüllen:


  // Iteration über einen Vector
  for (int i = 0; i < vector.size(); i++)
  {
     // Neue Zeile an Tabelle anhängen und auf
     // neue Zeile wechseln
     table.appendRow();

     // schreibe in erste Spalte
     table.setValue((String)vector.get(i),0);

     // schreibe in zweite Spalte
     table.setValue((String)vector.get(i),1);
  }

Nachdem eine Funktion ausgeführt wurde, also nachdem Connection.execute(funktion); ausgeführt wurde, kann eine neue Tabelle zurückgeliefert werden, oder eine bereits befüllte Tabelle neue Werte beinhalten.

Um über eine Rückgabetabelle zu iterieren, gibt es die Funktion setRow(index). Das folgende Beispiel zeigt die Suche nach einem bestimmten String in der 3. Spalte und liefert das Feld „ID“ zurück:


  String rueckgabe = null;
  for (int i=0;i<outputtabelle.getNumRows();i++)
  {
    outputtabelle.setRow(i);

    if (outputtabelle.getString(2).equals(suche) )
    {
      rueckgabe = outputtabelle.getString("ID");
    }
  }

Wie ersichtlich wird, lässt sich die Spalte nicht nur anhand des inkrementellen Indexes ansprechen, sondern auch über den Spaltennamen.

In manchen Fällen ist es nötig eine eigene Tabelle zu erzeugen und diese an einen Funktionsbaustein zu übergeben. Zum Beispiel funktioniert die Zuweisung einer befüllten Ergebnistabelle an eine Übergabetabelle nicht, in diesem Fall muss man die Daten in einer Schleife einfach rauskopieren.

Eine eigene Tabellendefinition erzeugt man in diesem Fall so:


  JCO.MetaData smeta  = new JCO.MetaData("DIS");

  smeta.addInfo("DOKAR",  JCO.TYPE_STRING,  3,  0, 0);
  smeta.addInfo("DOKVR",  JCO.TYPE_STRING ,   2, 0, 0);
  smeta.addInfo("DOKTL",  JCO.TYPE_STRING ,   3, 0, 0);
  smeta.addInfo("DOKNR",  JCO.TYPE_STRING ,   3, 0, 0);

  JCO.Structure structure = new JCO.Structure(smeta); 
  JCO.Table table = new JCO.Table(structure);

Struktur-Parameter

Strukturen gehören zu den Tabellen-Typ-Parametern und sind Sonderfälle. Eine Struktur kann innerhalb einer Tabelle, in Import- oder Export-Parametern auftreten. Hierbei handelt es sich lediglich um eine weitere Aufteilung innerhalb eines einzigen Feldes.

Der folgende Code zeigt, wie eine Referenz auf eine Inputstruktur und auf einen normalen Import-Parameter geholt wird .


JCO.Structure struktur =
func.getImportParameterList().getStructure("SELECT_DOCUMENTDATA");
JCO.ParameterList inputdata = func.getImportParameterList();
struktur.setValue(art, "DOCUMENTTYPE");
inputdata.setValue("X", "GETCLASSIFICATION");
Output.execute(funktion);

Fortsetzung folgt …