Problemy z sortowaniem korespondencji seryjnej

Question

Do mojej pracy domowej java staram się napisać klasę sortowania rekurencyjnego. W tej chwili mam 3 metody metodę "sterownika", aby uruchomić rekursję, metodę rekursywną mergeSort i metodę . W zależności od zmiennych, które zmieniam, moje dane wyjściowe są tablicą zer lub mojej oryginalnej tablicy w tej samej kolejności. Jedyną rzeczą jest oryginalna metoda mergeSort, która musi przyjmować jedną tablicę, a metoda merge nie może niczego zwrócić. Każda pomoc jest doceniana:

import java.util.Arrays; 
public class merge2 { 
    public static void main(String[] args){ 
     int []a={22,45,1,4,89,7,0}; 
     mergeSort(a); 
     System.out.println(Arrays.toString(a));     
    } 

    public static void mergeSort(int [] a){ 
     mergeSort(a,0,a.length-1); 
    } 

    public static void mergeSort(int []a, int beg,int end){ 
     if(beg<end){ 
      int mid=(beg+end)/2; 
      mergeSort(a,beg,mid); 
      mergeSort(a,mid+1,end); 
      merge(a,beg,mid,end); 
     } 
    } 

    private static void merge(int []a, int beg, int middle, int end){ 
     int [] d=new int[a.length]; 
     int mid=middle+1; //start of second half of array 
     for(int i=0;i<d.length;i++){ 
      if(beg<=middle && mid<=end){ 
       if(a[beg]<=a[mid]) { 
       d[i]=a[beg]; 
       beg++; 
       } else if(a[mid]<=a[beg]){ 
         d[i]=a[mid]; 
         mid++; 
       } 
      }else if(beg>middle){ 
       d[i]=a[mid]; 
       mid++; 
      }else if(mid==a.length){ 
       d[i]=a[beg]; 
       beg++; 
      } 
     } 
     for(int w=0;w<d.length;w++){ 
      a[w]=d[w]; 
     } 
    } 
} 

Answer 1

OK Naprawiłem twoje rozwiązanie. Twoim głównym problemem był on-line oznaczony //<= here. Gdy mid przejechał nad indeksem końcowym, nie przypisano wartości z a do d, więc zostało wypełnione 0. Aby rozwiązać ten problem, musisz zastąpić == przez >=.
Naprawiłem też twoją pracę z indeksami. Nie musisz biegać po całej tablicy na każdym poziomie. Również twoja złożoność cierpi w ten sposób. Myślę, że jest to około O(n^2). Wystarczy uruchomić tylko część tablicy, która jest przetwarzana na tym poziomie rekursji, aby zachować złożoność w zakresie O(nlog(n)).

algorytm Fixed następująco

public static void main(String[] args){ 
    int []a={22,45,1,4,89,7,0}; 
    mergeSort(a); 
    System.out.println(Arrays.toString(a)); 

} 

public static void mergeSort(int [] a){ 
    mergeSort(a,0,a.length-1); 
} 

public static void mergeSort(int []a, int beg,int end){ 
    if(beg<end){ 
     int mid=(beg+end)/2; 
     mergeSort(a,beg,mid); 
     mergeSort(a,mid+1,end); 
     merge(a,beg,mid,end); 
    } 
} 

private static void merge(int []a, int beg, int middle, int end){ 
    int [] d=new int[a.length]; 
    int mid=middle+1; //start of second half of array 
    int beg1=beg; 
    for(int i=beg1;i<=end;i++){ 
     if(beg<=middle && mid<=end){ 
      if(a[beg]<=a[mid]) { 
      d[i]=a[beg]; 
      beg++; 
      } else if(a[mid]<=a[beg]){ 
        d[i]=a[mid]; 
        mid++; 
      } 
     }else if(beg>middle){   
      d[i]=a[mid]; 
      mid++; 
     }else if(mid>=end){ //<= here 
      d[i]=a[beg]; 
      beg++; 
     } 
    } 
    for(int w=beg1;w<=end;w++){ 
     a[w]=d[w]; 
    } 
} 

Answer 2

Oto pseudokod dla metody mergeSort. Widzę, że masz pominąć przypadki bazowe dla jednego lub dwóch elementów:

if (sublist has only one value) 
    do nothing 
else if (sublist has two values) 
    switch if necessary 
else // recursion, divide list into two halves 
    Find midpoint of current sublist 
    Call mergeSort and process left sublist 
    Call mergeSort and process right sublist 
    merge left and right sublists 

Co do metody scalania, to tworzy nową tablicę zamiast modyfikowania istniejącej tablicy. Sugeruję użycie ArrayLists do implementacji:

private void merge(int[] a, int first, int mid, int last) 
    { 
    ArrayList<Integer> left = new ArrayList<Integer>(mid - first + 1), right = new ArrayList<Integer>(last - mid); 
    for(int m = first; m <= mid; ++m) //initialize left sublist 
    { 
     left.add(a[m]); 
    } 
    for(int m = mid + 1; m <= last; ++m) //initialize right sublist 
    { 
     right.add(a[m]); 
    } 
    int i = first; 
    while(!left.isEmpty() || !right.isEmpty()) //while either list has an element 
    { 
     if(left.isEmpty()) 
     { 
     a[i++] = right.remove(0); 
     } 
     else if(right.isEmpty()) 
     { 
     a[i++] = left.remove(0); 
     } 
     else if (left.get(0) < right.get(0)) 
     { 
     a[i++] = left.remove(0); 
     } 
     else 
     { 
     a[i++] = right.remove(0); 
     } 
    } 
    }