Schleifeninvariante finden bei Sortieralgorithmus

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • Schleifeninvariante finden bei Sortieralgorithmus

    Hallo,

    ich hab schon ein bisschen über Schleifeninvarianten recherchiert und weiß deshalb grob, was damit gemeint ist. Nur "klack" gemacht hat es noch nicht.
    Daher wollte ich euch um Hilfe beim Finden der Invariante des folgenden Codes bitten:

    Quellcode

    1. public static void Sort (int[]a) {
    2. for (int i = 0; i < a.length; i++) {
    3. for (int j=0 ; j < a.length; j++) {
    4. if (a[i] < a[j]) {
    5. int hilf = a[i];
    6. a[i] = a[j];
    7. a[j] = hilf;
    8. }
    9. }
    10. }
    11. }
    Alles anzeigen


    Es wäre toll, wenn mir jemand einen Denkanstoß geben könnte.
    Ich habe mir folgendes überlegt: "
    a[0… i]
    enthält die kleinsten Werte der Zahlen
    von 0 bis i sortiert."

    Das stimmt ja beim ersten Durchlauf für i = 0, da die Zahl ja nicht sortiert werden muss.

    Muss ich eigentlich zwei Schleifeninvarianten finden, da es eine doppelte Schleife ist?