Java Natural Merge Сортировка

Question

Я могу считать новым в Java. Я боролся с одним вопросом, который был дан нам нашим профессором в нашей школе. Я должен сделать естественный алгоритм сортировки слиянием, который должен каждый раз находить два отсортированных подматрицы и объединять их (что является версией сортировки слияния снизу вверх). Но я застрял здесь мой код

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); 
    } 
} 

, что происходит в том, что она не сливаясь правильно, и он идет в бесконечном цикле в цикле Outter, что, поскольку он не отсортирован должным образом. Есть ли кто-нибудь, кто может мне лучше посоветовать или сказать мне ошибку, которую я здесь делаю. Заранее спасибо.

Answer 1

Проблема заключается в середине расчета, я не совсем уверен, почему вы это делаете, но если в середине меньше, чем у меня, вы можете использовать метод слияния, и вы не сможете найти его без решения, при каждом запуске вам нужно подобрать два массива для сортировки, так что вместо середины вы можете вставить I к методу слияния, так что вы начинаете слияние с разлома в.

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 в исправляет проблемы с оригиналом код. Ниже приведены несколько альтернативных примеров, которые немного оптимизированы, сканирование массива для пар восходящих последовательностей, а не начало в начале каждого раза. Если массив был отменен, то первый проход создает прогоны 2, следующий проход проходит 4, .... С исходной версией размер прогона увеличивался бы только по одному на каждом цикле. В приведенном ниже примере используется открытый интервал (последний индекс - конец массива вместо последнего элемента массива).

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 
       } 
      } 
     } 
    } 

Нет копию обратно версию, а не сливается назад и вперед между двумя массивами, и только копиями в конце, если отсортированные данные заканчиваются в неверном массиве.

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 
       } 
      } 
     } 
    }