Wie funktionieren diese Methoden in diesem Sortierverfahren genau?

[bob651]

HI, ich habe vor mir einen Mergesort liegen und muss es kommentieren.
Das habe ich gemacht. Aber bei manchen Methoden verstehe ich es einfach nicht. Hier erstmal der Code.

public class algo1 {
   
    private int[] array1;
    private int[] array2;
    private int lange;
    public static int[] Zahlen;
    public static double summe;
  
    public void zerlegen(int inputArray[]) {
        this.array1 = inputArray;
        this.lange = inputArray.length;
        this.array2 = new int[lange];
        mergesort(0, lange - 1); //methode mergesort
    }
  
    private void mergesort(int links, int rechts) {
           
        if (links < rechts) {       
           //sortiert links bis rechts, wenn es mehr als 1 element hat
          
            int mitte = (links + rechts) / 2;
            // zerlegt die  Arrays in 2 hälften
          
            mergesort(links, mitte);
            // linke Hälfte sortieren
         
            mergesort(mitte + 1, rechts);
            //rechte Hälfte sortiren
         
            mischen(links, mitte, rechts);
            //alles zusammen mischen
        }
    }
  
    private void mischen(int links, int mitte, int rechts) {
          //methode mischt alle arrays
        for (int i = links; i <= rechts; i++) {   
         //solange rechts größer/gleich links -->links erhöhen
            array2[i] = array1[i];
        }
      
        int i = links;            //i durchläuft von links bis mid
        int j = mitte + 1;    //j durchläuft von mid bis rechts
        int k = links;           //k durchläuft von links nach rechts
     
      
    
      
        while (i <= mitte && j <= rechts) {       
           //solange keine der beiden Arrays ganz durchlaufen sind
            if (array2[i] <= array2[j]) {
                array1[k] = array2[i];
                i++;
            } else {
                array1[k] = array2[j];
                j++;
            }
            k++;
        }
    
      
        while (i <= mitte) {                
           //Rest von links wird durchlaufen
            array1[k] = array2[i];
            k++;
            i++;
        }
     
    }
    }
  

    public static void main(String a[]) throws Exception{
        setUp();
        algo1 neuearray = new algo1();
        neuearray.zerlegen(Zahlen);
        //Array mit Zahlen erstellen
     
        for(int i:Zahlen){
            System.out.print(i);
            System.out.print(" ");
        }

    }

public static void setUp() throws Exception{
    File Text.txt = new File ("D:/Users/or/workspace/aab/src/abc/Text.txt");
    Zahlen = zahlenleser.FileToIntArray(Text.txt);

Hoffe das ist nicht zu lang.
Also ich habe die Methode "mischen" zwar kommentiert, weiß aber nicht wirklich wie es geht.
Und die Methode "zerlegen" habe ich auch nicht verstanden.
Es wäre echt eine riesen Hilfe, wenn sich jemand kurz Zeit nimmt und es mir kurz erklärt. Das wäre mega.

 

[Robat]

Die Methode zerlegen würde ich so kommentieren:

   /**
     * Zerlegt ein Array in 2 Hälften
     * (bzw eigentlich wird nur ein Array mit identischer Länge erstellt)
     *
     * @param inputArray
     */
    public void zerlegen(int inputArray[]) {
        // array1 als Synonym für den ursprünglichen Input
        this.array1 = inputArray;
     
        // die Länge / Anz. der Elemente / Anz. der Zahlen bekommen
        this.lange = inputArray.length;
     
        // ein neues Arrray der selben länge anlegen
        this.array2 = new int[lange];
     
        // die Methode mergesort aufrufen, mit dem Anfangswert 0 und dem
        // Endwert lange - 1 .. 
        //-1 weil man bei 0 Anfängt mit zählen..
        // wir zählen 1,2,3.. n.. in einem Array wird 0,1,2,..,n-1 gezählt
        mergesort(0, lange - 1); //methode mergesort
    }
    // Ergänzend zu dem mergesort:
    //
    // Es wird geprüft, ob das Array aus min. 2 Elementen besteht.
    // Wenn das der Fall ist, wird die Mitte des Array bestimmt. Durch
    // rekursiven aufruf der Methode mergesort wird erst die untere Hälfte
    // des Array sortiert und danach die obere Hälfte.
    //
    // Danach werden die beiden sortierten Hälften in "mischen" mit einander
    // verschmolzen.
    //
    // BSP Array:
    //|7|1|2|9|2|4|9|6|7|9
    //
    // Aufteilen:
    // |7|1|2|9|2  |4|9|6|7|9
    //
    // links sortieren:
    // |1|2|2|7|9
    //
    // rechts sortieren:
    // |4|6|7|9|9
    //
    // @see mischen
    private void mergesort(int links, int rechts) {
          
        if (links < rechts) {     
           //sortiert links bis rechts, wenn es mehr als 1 element hat
        
            int mitte = (links + rechts) / 2;
            // zerlegt die  Arrays in 2 hälften
        
            mergesort(links, mitte);
            // linke Hälfte sortieren
        
            mergesort(mitte + 1, rechts);
            //rechte Hälfte sortiren
        
            mischen(links, mitte, rechts);
            //alles zusammen mischen
        }
    }

Also ich würde die mischen -Methode so kommentieren:

/**
     * Methode um Elemente eines Arrays zu sortieren.
     *
     * @param links
     * @param mitte
     * @param rechts
     */
    private void mischen(int links, int mitte, int rechts) {
     
        // Kopiere die Elemente aus array1 in array2
        // damit man array1 also "neues"-sortiertes Array nutzen kann
        for (int i = links; i <= rechts; i++) {
            array2[i] = array1[i];
        }
   
        int i = links;            // i = links = 0; (1.Index d. Arrays )
        int j = mitte + 1;        // j = mitte + 1 (1. Index nach der Hälfte)
        int k = links;            // k = links = 0;
   
   
 
        // Vergleiche die Elemente der linken Seite des Arrays
        // mit den Elementen der rechten Seite des Arrays
        // Bsp:
        //Array:
        //|1|2|2|7|9  |4|6|7|9|9
        // x y z       x y z
        // Es wird also immer x mit x vergleichen, y mit y.. usw
        while (i <= mitte && j <= rechts) {    
           //solange keine der beiden Arrays ganz durchlaufen sind
         
           //   x,y,z        y,y,z
           if (array2[i] <= array2[j]) {
                // wenn das linke Element kleiner ist als das rechte Element
                // schreibe das linke Element in das "neue" - sortierte Array
                array1[k] = array2[i];
                // gehe ein Element im linken Array weiter
                i++;
            } else {
                // wenn das rechte Element kleiner ist als das linke Element
                // schreibe das rechte Element in das "neue" - sortierte Array
                array1[k] = array2[j];
                // gehe ein Element im rechten Array weiter
                j++;
            }
            // erhöhe den Index für das "neue"-sortiere Array, weil die Zahl für
            // den Index ja gefunden wurde.
            k++;
        }
        // Danach würde das Bsp Array also so aussehen:
        // |1|2|2|4|6|7|7|9|9|9
        //
        //
        //
        // Wenn eine der beiden Zählvariablen i oder j am "Ende" ist (d.h. wenn
        // i an der Hälfte angekommen ist bzw j am Ende des Arrays, dann bleibt
        // ein "Rest" an Zahlen übrig die noch nicht kopiert wurden (ins neue Array)
 
        // das zurückkopieren in das neue Array geschiet hier
        while (i <= mitte) {              
           //Rest von links wird durchlaufen
            array1[k] = array2[i];
            k++;
            i++;
        }
   
    }

Vielleicht hilft es ja.

Gruß
Robert

 

[bob651]

Robat bester Mann. Danke für alles. <3. Hoffe ich verstehe es jetzt