Java Natural Merge Sort Implementierung

Question

Ich kann in Java als neu betrachtet werden. Ich habe mit einer Frage gekämpft, die uns von unserem Professor an unserer Schule gestellt wurde. Ich sollte einen natürlichen Merge-Sort-Algorithmus erstellen, der jedes Mal zwei sortierte Sub-Arrays finden und diese zusammenführen muss (was eine Version von Bottom-Up-Merge-Sort ist). Aber ich steckte hier ist mein Code

public class NaturalMergeMine { 
    private static Comparable[] aux; 

    public static void sort(Comparable[] a) { 
    aux = new Comparable[a.length]; 
    sort(a, 0, a.length - 1); 
    } 

    public static boolean isSorted(Comparable[] a) { 
    for (int i = 1; i < a.length; i += 1) { 
     if (a[i - 1].compareTo(a[i]) < 0) { 
     return false; 
     } 
    } 
    return true; 
    } 

    private static void sort(Comparable[] a, int lo, int hi) { 
    int i = lo; 
    int j = 0; 
    int mid = 0; 
    int az = 0; 

    while (true) { 
     i = 0; 
     System.out.println("outter"); 
     while (i < a.length) { 
     System.out.println("inner 1"); 
     if (i == a.length - 1) { 
      break; 
     } else if (a[i].compareTo(a[i + 1]) < 0) { 
      break; 
     } 
     i++; 
     } 

     j = i + 1; 

     while (j < a.length) { 
     System.out.println("inner 2"); 
     if (j == a.length - 1) { 
      break; 
     } else if (a[j].compareTo(a[j + 1]) < 0) { 
      break; 
     } 
     j++; 
     } 
     mid = lo + (j - lo)/2; 
     Merge(a, lo, mid, j); 
     lo = 0; 

     if (isSorted(a)) { 
     break; 
     } 
    } 
    } 

    public static void Merge(Comparable[] a, int lo, int mid, int hi) { 
    int i = lo; 
    int j = mid + 1; 

    for (int k = lo; k <= hi; k++) { 
     aux[k] = a[k]; 
    } 

    for (int k = lo; k <= hi; k++) { 
     if (i > mid) { 
     a[k] = aux[j++]; 
     } else if (j > hi) { 
     a[k] = aux[i++]; 
     } else if (aux[i].compareTo(aux[j]) < 0) { 
     a[k] = aux[j++]; 
     } else { 
     a[k] = aux[i++]; 
     } 
    } 
    } 

    public static void show(Comparable[] a) { 
    for (int i = 0; i < a.length; i++) { 
     System.out.print(a[i] + " "); 
    } 
    } 

    public static void main(String[] args) { 
    Integer[] arr = {6, 4, 5, 7, 8, 3, 2, 1}; 
    sort(arr); 
    show(arr); 
    } 
} 

, was passiert, ist, dass es nicht richtig verschmilzt und es geht in einer Endlosschleife in der äußer-Schleife, die ist, weil es nicht richtig sortiert ist. Gibt es jemanden, der mir einen besseren Weg geben kann oder mir den Fehler erzählen kann, den ich hier mache? Danke im Voraus.

Answer 1

Das Problem ist in der Mitte der Berechnung, ich bin nicht ganz sicher, warum Sie das tun, aber wenn die Mitte ist weniger als ich in Merge-Methode Sie nicht erreichen den Fehler Fall, so dass Sie bei der Entdeckung es ohne zu lösen, für jeder laufen müssen Sie zwei Arrays abholen zu sortieren, so dass anstelle der Mitte können Sie i zur merge Methode einfügen, so dass Sie das verschmelzen von dem Fehler in starten.

public class NaturalMergeMine { 
private static Comparable[] aux; 

public static void sort(Comparable[] a) { 
    aux = new Comparable[a.length]; 
    sort(a, 0, a.length - 1); 
} 

public static boolean isSorted(Comparable[] a) { 
    for (int i = 1; i < a.length; i += 1) { 
    if (a[i - 1].compareTo(a[i]) > 0) {//changed operator to greater than 
     return false; 
    } 
    } 
    return true; 
} 

private static void sort(Comparable[] a, int lo, int hi) { 
    int i = lo; 
    int j = 0; 
    int mid = 0; 
    int az = 0; 

    while (true) { 
    i = 0; 
    System.out.println("outter"); 
    while (i < a.length) { 
    System.out.println("inner 1"); 
    if (i == a.length - 1) { 
     break; 
     } else if (a[i].compareTo(a[i + 1]) > 0) {//changed operator to greater than 
     break; 
     } 
     i++; 
    } 

    j = i + 1; 

    while (j < a.length) { 
    System.out.println("inner 2"); 
    if (j == a.length - 1) { 
     break; 
    } else if (a[j].compareTo(a[j + 1]) > 0) {//changed operator to greater than 
     break; 
    } 
    j++; 
    } 
//  mid = lo + (j - lo)/2; 
    Merge(a, lo, i, j); 
    lo = 0; 

    if (isSorted(a)) { 
    break; 
    } 
} 
} 

public static void Merge(Comparable[] a, int lo, int mid, int hi) { 
int i = lo; 
int j = mid + 1; 

for (int k = lo; k <= hi; k++) { 
    aux[k] = a[k]; 
} 

for (int k = lo; k <= hi; k++) { 
    if (i > mid) { 
    a[k] = aux[j++]; 
    } else if (j > hi) { 
    a[k] = aux[i++]; 
    } else if (aux[i].compareTo(aux[j]) > 0) {//changed the operator to greater than 
    a[k] = aux[j++]; 
    } else { 
    a[k] = aux[i++]; 
    } 
} 
} 

    public static void show(Comparable[] a) { 
    for (int i = 0; i < a.length; i++) { 
    System.out.print(a[i] + " "); 
    } 
    } 

public static void main(String[] args) { 
    Integer[] arr = {6, 4, 5, 7, 8, 3, 2, 1}; 
    sort(arr); 
    show(arr); 
    } 
} 

Answer 2

Amer Qarabsa Antwort, die Probleme mit dem Original fixiert Code. Im Folgenden sind einige alternative Beispiele aufgeführt, die etwas optimierter sind, indem das Array nach Paaren aufsteigender Sequenzen durchsucht wird, anstatt jedes Mal zu Beginn neu zu beginnen. Wenn das Array umgekehrt wurde, erzeugt der erste Durchlauf Läufe von 2, der nächste Durchlauf Läufe von 4, .... Bei der ursprünglichen Version würde die Laufgröße in jeder Schleife nur um eins erhöht. Der folgende Beispielcode verwendet offene Intervalle (der letzte Index ist das Ende des Arrays anstelle des letzten Elements des Arrays).

public class jsortns { 
    private static Comparable[] aux; 

    public static void sort(Comparable[] a) { 
     aux = new Comparable[a.length]; 
     int i; 
     int j; 
     int k; 
     while (true) {     // merge pass 
      i = 0; 
      while(true) {    // find, merge pair of runs 
       j = i;     // find left run 
       while (++j < a.length) { 
        if (a[j-1].compareTo(a[j]) > 0) 
         break; 
       } 
       if(j == a.length){  // if only one run left 
        if(i == 0)   // if done return 
         return; 
        else    // else end of merge pass 
         break; 
       } 
       k = j;     // find right run 
       while (++k < a.length) { 
        if (a[k-1].compareTo(a[k]) > 0){ 
         break; 
        } 
       } 
       Merge(a, i, j, k);  // merge runs 
       i = k; 
       if(i == a.length)  // if end of merge pass, break 
        break; 
      } 
     } 
    } 

    // merge left and right runs 
    // ll = start of left run 
    // rr = start of right run == end of left run 
    // ee = end of right run 
    public static void Merge(Comparable[] a, int ll, int rr, int ee) { 
     int i = ll; 
     int j = rr; 
     int k; 
     for (k = ll; k < ee; k++) 
      aux[k] = a[k]; 
     k = ll; 
     while(true){ 
      // if left element <= right element 
      if (aux[i].compareTo(aux[j]) <= 0) { 
       a[k++] = aux[i++];  // copy left element 
       if(i == rr){   // if end of left run 
        while(j < ee)  // copy rest of right run 
         a[k++] = aux[j++]; 
       return;     // and return 
       } 
      } else { 
       a[k++] = aux[j++];  // copy right element 
       if(j == ee){   // if end of right run 
        while(i < rr){  // copy rest of left run 
         a[k++] = aux[i++]; 
        } 
       return;     // and return 
       } 
      } 
     } 
    } 

Keine Kopie zurück Version verschmilzt stattdessen hin und her zwischen zwei Arrays und kopiert nur am Ende, wenn die sortierten Daten in der falschen Reihe enden.

public class jsortns { 
    private static Comparable[] b;  // temp array 
    private static Comparable[] o;  // original array reference 
    private static Comparable[] t;  // used to swap a, b 

    public static void sort(Comparable[] a) { 
     o = a;       // save ref to a 
     b = new Comparable[a.length]; // allocate temp array 
     int i; 
     int j; 
     int k; 
     while (true) {     // merge pass 
      i = 0; 
      while(true) {    // find, merge pair of runs 
       j = i;     // find left run 
       while (++j < a.length) { 
        if (a[j-1].compareTo(a[j]) > 0) 
         break; 
       } 
       if(j == a.length){  // if only one run left 
        if(i != 0){   // if not done 
         while(i < j){ //  copy run to b 
          b[i] = a[i]; 
          i++; 
         } 
         break;   // break to end merge pass 
        } else {   // else sort done 
         if(a != o){  // if a not original a, copy 
          for(i = 0; i < a.length; i++) 
           b[i] = a[i]; 
         } 
         return; 
        } 
       } 
       k = j;     // find right run 
       while (++k < a.length) { 
        if (a[k-1].compareTo(a[k]) > 0){ 
         break; 
        } 
       } 
       Merge(a, b, i, j, k); // merge left, right into b 
       i = k; 
       if(i == a.length)  // break if end pass 
        break; 
      } 
      t = a;      // swap a and b (references) 
      a = b; 
      b = t; 
     } 
    } 

    // merge left and right runs from a[] to b[] 
    // ll = start of left run 
    // rr = start of right run == end of left run 
    // ee = end of right run 
    public static void Merge(Comparable[] a, Comparable[] b, int ll, int rr, int ee) { 
     int i = ll; 
     int j = rr; 
     int k = ll; 
     while(true){ 
      // if left element <= right element 
      if (a[i].compareTo(a[j]) <= 0) { 
       b[k++] = a[i++];  // copy left element 
       if(i == rr){   // if end of left run 
        while(j < ee)  // copy rest of right run 
         b[k++] = a[j++]; 
       return;     // and return 
       } 
      } else { 
       b[k++] = a[j++];  // copy right element 
       if(j == ee){   // if end of right run 
        while(i < rr){  // copy rest of left run 
         b[k++] = a[i++]; 
        } 
       return;     // and return 
       } 
      } 
     } 
    }