Laufzeit ermitteln, einfacher Sortieralgorithmus

[NefetsClaxon]

Hallo!

Versuche gerade, die Laufzeit eines einfachen Algorithmus zu bestimmten, anhand des folgenden Beispiels:

https://www.tu-ilmenau.de/fileadmin/...uD-SS09-01.pdf (S.18, "Die Laufzeit von Straight Insertion Sort")

Zuerstmal glaube ich, dass der Algorithmus dort falsch ist. Wenn ich den so programmiere, wird mein Array nicht richtig sortiert: bei Array, dass von 10 bis 1 geht, wird die 10 nicht berücksichtigt. Die korrekte Implementierung sollte die folgende sein:

  final int[] p = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
        // final int[] p = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
        int counterone = 0;
        int countertwo = 0;
        int x;
        int j;
        
        final int n = p.length;
        
        for (int i = 1; i < n; i++) {
            System.out.println("Außen Durchlauf Nr.:" + ++counterone);
            x = p[i];
            j = i;
            while (j > 0 && x < p[j - 1]) {
                System.out.println("         Innen Durchlauf Nr.:"
                        + ++countertwo);
                p[j] = p[j - 1];
                j--;
            }
            p[j] = x;
        }

(so ist es auch hier umgesetzt:; http://www.brpreiss.com/books/opus4/html/page489.html)

Ich komme dann auch auf eine andere Laufzeit (S.19)

- im best case würde ich sagen, einfach n-mal: Die äußere Schleife wird für jedes Array-Element einmal durchlaufen aber die innere wird nie ausgeführt.
- im worst case: 5*(n-1)+ n*(i * 4)

> die äußere Schleife wird im worst case (n-1)-mal durchlaufen, es finden 5 Elementaroperationen statt: 1 Vergleich (i < n), 1 Inkrementierung (i++) und 3 Zuweisungen
> die innere Schleife wird im worst case i-mal durchlaufen (also erst 1mal, dann 2mal, dann 3mal,...), dort finden 4 Elementaroperationen stat (zwei Vergleiche,1 Zuweisung und 1 Dekrementierung), das ganze n mal (also (1 * 4) + (2 * 4) + (3 * 4) ...)

Ist das annähernd richtig?

Und falls der Algorithmus auf der Folie doch richtig sein sollte: Wieso wird denn die äußere Schleife n-mal durchlaufen, wenn die Schleife von 2 bis n geht?

Wäre super, wenn sich da jemand kurz Zeit nehmen könnte!

[Ralf Jansen]

Beide Algorithmen scheinen korrekt. Um eine Kette von n Elementen zu vergleichen brauche ich n-1 Vergleiche nicht n (ich spar mir die Erklärung wenn du mal kurz drüber nachdenkst sollte sich die Logik dahinter offenbaren).
Du vergleichst von 1 bis N-1 in einem 0-basierten Array. Den Algo den du für falsch hältst geht aber von einem 1-basierten Array aus und vergleicht deshalb von 2 bis N. Die gleiche Anzahl von vergleichen nur die Indizes sind unterschiedlich.

im best case würde ich sagen, einfach n-mal: Die äußere Schleife wird für jedes Array-Element einmal durchlaufen aber die innere wird nie ausgeführt.

Genau eigentlich n-1 mal und nicht n-mal. Eine bereits sortierte Liste würde n-1 Schleifendurchläufe benötigen. Für eine Komplexitätsbetrachtung können wir aber einfach von n-mal ausgehen. Als O(n)

im worst case: 5*(n-1)+ n*(i * 4)

i ist keine Eingabevariable des Algorithmus (es ist eine innere Variable) die kannst du hier für eine Aussage über die Komplexität nicht benutzen. Wie auch i ist irgendwas zwischen 1 und n-1.

im ungünstigsten Fall eine umgekehrt sortierte Liste hast du für die inner Schleife (n-1) + (n-2) + (n-3) usw. Durchläufe bis der Summand n-x zu 1 wird. Wenn du dich an die Gaußsche Summenformel erinnerst entspricht das (n^2+n)/2 (Wir ignorieren das hier einmal n fehlt) . Bei der Komplexitätsbetrachtung interessiert nur der Wert mit dem höchsten Exponenten hier als n^2. n und der Faktor 1/2 sind also interessant. Der ungünstigste Fall ist somit O(n^2).