QuickSort Verständis Problem (?)

[R0flC0pterpiL0t]

Hallo guten Abend, ich versuche mich kurz zu fassen.

Ich habe einen QuickSort-Algorithmus geschrieben.

Verstanden habe ich ihn eigentlich - würde ich jetzt mal behaupten - doch um sicherzugehen, habe ich versucht jeden einzelnen Schritt nachzuvollziehen. Hat ziemlich lange geklappt, doch dann...
bin ich auf etwas mir sehr Komisches gestoßen. Ganz plötzlich wird einfach die Variable untereGrenze von eben noch 1 auf 19 gesetzt?! Habe versucht, den "Fehler" (ist ja kein Fehler, der Algorithmus funktioniert ja) durch Ausprobieren, ab wann die Variable geändert wird, zu finden, doch ja... keine Ahnung worans liegt.

Ich glaube, das Bild erklärt alles.

Kann mir das jemand erklären? ???:L Ich weiß echt nicht mehr weiter ...


edit: habs mir weiter angeschaut... hab bemerkt, dass aus dem einen Ausgabebefehl von "obereGrenze" zwei Ausgaben kommen... einmal die 1, und einmal die 9 mit der die if-Schleife erfüllt wird, und weiter arbeitet...

aber wie kommt er auf die 9?? Das ist doch Schummeln!

edit2:

vielleicht nützt euch mein Quellcode ja etwas:

class QuickSort_notizen2
{
  public static void main(String[] args)
  {
    System.out.println("*************************");
    System.out.println("********QUICKSORT********");
    System.out.println("*************************");
    System.out.println();
    
    int a[] = {43,56,54,76,12,78,23,12,90,75};
    System.out.print("Unsortiert: ");
    ausgeben(a);
    System.out.println();
    
    quicksort(a);
    
    System.out.println();
    System.out.println();
    System.out.print("Sortiert:   ");
    ausgeben(a);
    System.out.println();
  }  
  
  public static void quicksort(int[] liste)
  {
    int untereGrenze = 0;
    int obereGrenze = liste.length-1;
    //obereGrenze = 10-1 = 9
    quicksort(liste, untereGrenze, obereGrenze);   
  }
  
  private static void quicksort(int[]liste, int untereGrenze, int obereGrenze)
  {
    int links = untereGrenze;
    //1. links = 0
    //32. links = 0
    int rechts = obereGrenze;
    //2. rechts = 9
    //33. rechts = 1, obereGrenze=1 
    int pivot = liste[((untereGrenze + obereGrenze)/2)];
    //3. pivot = liste[9/2=4] = 12
    //34. pivot = liste[1/2=0] = 12
    do {
      System.out.println();
      System.out.print("            ");
      for (int i=0;i<liste.length-1;i++) 
      {
        System.out.print(liste[i]+","); 
      } // end of for
      System.out.println(liste[liste.length-1]);
      System.out.print("                      ");
      //ausgabe#1 liste={43,56,54,76,12,78,23,12,90,75}
      //ausgabe#2 {12,56,54,76,12,78,23,43,90,75}
      //ausgabe#3 {12,12,54,76,56,78,23,43,90,75}
      //ausgabe#4 {12,12,54,76,56,78,23,43,90,75} (übergebene liste)
      System.out.println(liste[untereGrenze]+","+pivot+","+liste[obereGrenze]);
      //ausgabe#1 liste[0]=43, pivot=12, liste[9]=75
      //ausgabe#2 liste[0]=12, pivot=12, liste[9}=75
      //ausgabe#3 liste[0]=12, pivot=12, liste[9}=75
      //ausgabe#4 liste[0]=12, pivot=12, liste[1]=12, -->obereGrenze=1
      System.out.print("                    ");
      System.out.println("["+untereGrenze+"],["+(untereGrenze+obereGrenze)/2+"],["+obereGrenze+"]");
      //ausgabe#1 [0], [4], [9]
      //ausgabe#2 [0], [4], [9]
      //ausgabe#3 [0], [4], [9]
      //ausgabe#4 [0], [0], [1] -->obereGrenze=1
      System.out.print("                       ");
      System.out.println(links+","+pivot+","+rechts);
      //ausgabe#1 0, 12, 9
      //ausgabe#2 1, 12, 6
      //ausgabe#3 2, 12, 3
      //ausgabe#4 0, 12, 1 --> links=0, rechts=1
      
      while (liste[links]<pivot)
      //4. liste[0]=43<12 - überspringe anweisung
      //13. liste[1]=56<12 - überspringe anweisung
      //22. liste[2]=54<12 - überspringe anweisung
      //35. liste[0]=12<12 - überspringe anweisung
      { 
        links++; 
      } // end of while
      while (liste[rechts]>pivot)
      //5. liste[9}=75>12 - führe anweisung aus
      //7. liste[8]=90>12 - führe anweisung aus
      //9. liste[7]=12>12 - überspringe anweisung, rechts=7
      //14. liste[6]=23>12 - führe anweisung aus
      //16. liste[5]=78>12 - führe anweisung aus
      //18. liste[4]=12>12 - überspringe anweisung, rechts = 4
      //23. liste[3]=76>12 - führe anweisung aus
      //25. liste[2]=54>12 - führe anweisung aus
      //27. liste[1]=12>12 - überspringe anweisung
      //36. liste[1]=12>12 - überspringe anweisung  
      {
        rechts--;
        //6. rechts = 8
        //8. rechts = 7
        //15. rechts = 5
        //17. rechts = 4 
        //24. rechts = 2
        //26. rechts = 1  
      }
      if (links<=rechts)
      //10. 0<=7 - führe anweisung aus
      //19. 1<=4 - führe anwisung aus
      //28. 2<=1 - überspringe anweisung
      //37. 0<=1 - führe anweisung aus 
      {
        int tmp = liste[links];        
        liste[links] = liste[rechts];   
        liste[rechts]=tmp;               
        links++;                   
        rechts--;
        //11. temp = liste[0] = 43, liste[0] = 12, liste[7] = 43,
        //links = 1, rechts = 6
        // --> {12,56,54,76,12,78,23,43,90,75}
        //20. temp = liste[1] = 56, liste[1] = liste[4] =12, liste[4]=56
        //links = 2, rechts = 3
        // --> {12,12,54,76,56,78,23,43,90,75}
        //38. temp = liste[0]= 12, liste[0]=liste[1]=12, liste[1]=12
        //links=1, rechts=0
        
        System.out.println(links+","+rechts+","+obereGrenze);
                         
      } // end of if
    } while (links<=rechts);
    //12. 1<=6 - führe do aus
    //21. 2<=3 - führe do aus
    //29. 2<=1 - beende do
    //38. 1<=0 - beende do
    if (untereGrenze<rechts)
    //30. 0<1 - führe anweisung aus
    //39. 0<0 - überspringe anweisung
    {
      quicksort(liste,untereGrenze, rechts);
      //31.übergebe quicksort liste[]={12,12,54,76,56,78,23,43,90,75}
      //   untereGrenze=0, rechts=1
    }
    System.out.println("obereGrenze: "+obereGrenze);
    if (links<obereGrenze)
    //41. 1<1 ??? obereGrenze=1, und dann plötzlich 9 ??? 
    {
      quicksort(liste, links, obereGrenze); //<--- muss eigentlich doch jetzt ausgeführt werden?
    } // end of if
  }
  
  
  
  public static void füllen(int b[])
  {
    for (int i=0;i<b.length;i++) 
    {
      b[i]=(int)(Math.random()*100+1); 
    } // end of for
  }
  
  public static void ausgeben(int b[])
  {
    for (int i=0;i<b.length-1;i++) 
    {
      System.out.print(b[i]+","); 
    } // end of for
    System.out.print(b[b.length-1]);
  }
}

 

[R0flC0pterpiL0t]

Da ich den Editierbutton nicht mehr finde, schreibe ich einfach mal einen neuen Beitrag...

habe nun weitere 2 Stunden an diesem Verständnisproblem gesessen (sry für die Überschrift :s), und habe nun einen bisschen ausführlicher die Arbeitsweise von QuickSort beschreibenden Quellcode geschrieben.

PS: Es handelt sich um das Quicksort, dass das Pivot-Element durch die Mitte des Arrays bestimmt.

Mein Quellcode sieht nun wie folgt aus:

class QuickSort_notizen3
{
  public static void main(String[] args)
  {
    System.out.println("*************************");
    System.out.println("********QUICKSORT********");
    System.out.println("*************************");
    System.out.println();
    
    int a[] = {43,56,54,76,12,78,23,12,90,75};
    System.out.print("Unsortiert: ");
    ausgeben(a);
    System.out.println();
    
    quicksort(a);
    
    System.out.println();
    System.out.println();
    System.out.print("Sortiert:   ");
    ausgeben(a);
    System.out.println();
  }
  public static void quicksort(int[] liste)
  {
    System.out.println();
    System.out.println("quicksort (int[] liste) wird ausgeführt...");
    //45. annahme: liste wird übertragen...
    //---> {12,12,54,76,56,78,23,43,90,75}
    int untereGrenze = 0;
    //1. untereGrenze=0
    //46. untereGrenze=0
    System.out.println("untereGrenze:"+untereGrenze);
    int obereGrenze = liste.length-1;
    //2. obereGrenze = 10-1 = 9
    System.out.println("obereGrenze:"+obereGrenze);
    quicksort(liste, untereGrenze, obereGrenze);   
  }
  
  private static void quicksort(int[]liste, int untereGrenze, int obereGrenze)
  {
    System.out.println();
    System.out.println("quicksort(int[]liste, int untereGrenze, int obereGrenze) wird ausgeführt...");
    System.out.println();
    for (int i=0;i<liste.length-1;i++ ) 
    {
      System.out.print(liste[i]+",");  
    } // end of for
    System.out.println(liste[liste.length-1]);
    
    System.out.println("untereGrenze:"+untereGrenze+", obereGrenze:"+obereGrenze);
    //3.untereGrenze=0, obereGrenze=9
    //34. untereGrenze=0, obereGrenze=1
    int links = untereGrenze;
    System.out.print("links:"+links+",");
    //4.links=0
    //35. links=0
    int rechts = obereGrenze;
    System.out.println("rechts:"+rechts);
    //5.rechts=9
    //36. rechts=1
    int pivot = liste[((untereGrenze + obereGrenze)/2)];
    System.out.println("pivot:"+pivot);
    //6. pivot = liste[9/2=4]=12
    //37. pivot = liste[1/2=0]=12
    do {
      while (liste[links]<pivot)
      //7. 43<12 - überspringe anweisung
      //16. 56<12 - überspringe anweisung
      //24. 54<12 - überspringe anweisung
      //38. 12<12 - überspringe anweisung
      { 
        links++;
        System.out.println("links:"+links);  
      } // end of while
      while (liste[rechts]>pivot)
      //8. 75>12 - führe anweisung aus
      //10. 90>12 - führe anweisung aus
      //12. 12>12 - überspringe anweisung, rechts = 7
      //17. 23>12 - führe anweisung aus
      //19. 78>12 - führe anweisung aus
      //20. 12>12 - überspringe anweisung, rechts = 4
      //25. 76>12 - führe anweisung aus
      //27. 54>12 - führe anweisung aus
      //29. 12>12 - überspringe anweisung, rechts = 1
      //39. 12>12 - überspringe anweisung, rechts = 1
      {
        rechts--;
        System.out.println("rechts:"+rechts);
        //9. rechts=8 - wiederhole while
        //11. rechts=7 - wiederhole while
        //18. rechts=5 - wiederhole while
        //20. rechts=4  - wiederhole while
        //26. rechts=2 - wiederhole while
        //28. rechts=1 - wiederhole while
      }
      if (links<=rechts)
      //13. 0<=7 - führe anweisung aus
      //21. 1<=4 - führe anweisung aus
      //30. 2<=1 - überspringe anweisung
      //40. 0<=1 - führe anweisung aus 
      {
        int tmp = liste[links];
        liste[links] = liste[rechts];
        liste[rechts]=tmp;
        links++;
        rechts--;
        System.out.println("tausch... links:"+links+",rechts:"+rechts);
        //14. liste[0]=12, liste[7]=43, links=1, rechts=6
        //--> {12,56,54,76,12,78,43,90,75}
        //22. liste[1]=12, liste[4]=56, links=2, rechts=3
        //--> {12,12,54,76,56,78,23,43,90,75}
        //41. liste[0]=12, liste[1]=12, links=1, rechts=0
        //--> {12,12,54,76,56,78,23,43,90,75}
        for (int i=0;i<liste.length;i++) 
        {
          System.out.print(liste[i]+" ");  
        } // end of for
      } // end of if
      System.out.println();
    } while (links<=rechts);
    //15. 1<=6 - führe do aus
    //23. 2<=3 - führe do aus
    //31. 2<=1 - mache weiter mit programmcode
    //42. 1<=0 - mache weiter mit programmcode
    System.out.println("untereGrenze:"+untereGrenze+"rechts:"+rechts);
    if (untereGrenze<rechts)
    //32. 0<1 - führe anweisung aus
    //43. 0<0 - überspringe Anweisung 
    {
      System.out.println("untereGrenze<rechts-->quicksort(liste,untereGrenze,rechts) wird ausgeführt...");
      quicksort(liste,untereGrenze, rechts);
      //33. übergabe der werte ...  
    } // end of if
    System.out.println("obereGrenze:"+obereGrenze+"links:"+links);
    if (links<obereGrenze)
    //44. 1<1 - überspringe anweisung
    
    {
      System.out.println("links<obereGrenze-->quicksort(liste,links,obereGrenze) wird ausgeführt...");
      quicksort(liste, links, obereGrenze);  
    } // end of if
  }
  
  
  public static void füllen(int b[])
  {
    for (int i=0;i<b.length;i++) 
    {
      b[i]=(int)(Math.random()*100+1); 
    } // end of for
  }
  
  public static void ausgeben(int b[])
  {
    for (int i=0;i<b.length-1;i++) 
    {
      System.out.print(b[i]+","); 
    } // end of for
    System.out.print(b[b.length-1]);
  }
}

auf dem Bild erkennt man mein Problem. Ich habe den Quellcode so ausführlichst wie möglich veranschaulicht. Also immer dort, wo eine Variable geändert werden kann vom Compiler, einen Ausgabebefehl gesetzt, so dass ich das sehen kann im DOS-Fenster. Doch trotzdem scheint es so, als wenn der Compiler einfach mal so die Variable obereGrenze von 1 auf 9 setzt und so die rot markierte if-Abfrage erfüllt wird? Find ich extrem mysteriös.

 

[R0flC0pterpiL0t]

So... habe das Geheimnis gelüftet.

Er befand sich ja in einem Rekursionsvorgang (1.), und wenn dieser ja den ganzen Funktions-/Methodenkörper durchläuft (2.), ist dieser ja zu Ende (3.) und verlässt diese if-Anweisung, weil diese ja eben "fertig" ist. So läuft der Quellcode weiter mit links=2, untereGrenze=9 (5.)
Also ist die zweite if-Abfrage wahr, und der Quellcode sortiert munter weiter (6.)