マージソートの問題

Question

私のJavaの宿題のために、私は再帰的なマージソートクラスを書くのに苦労しています。現在、再帰を開始する3つのメソッド「ドライバ」メソッド、再帰的なmergeSortメソッド、およびmergeメソッドがあります。どのような変数を変更するかによって、出力はすべて0の配列か、元の配列と同じ順番になります。唯一のことは、元のmergeSortメソッドは1つの配列で取る必要があり、mergeメソッドは何も返すことができません。多くの助けを借りて助けてください

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ソリューションを修正しました。あなたの主な問題は//<= hereと記されていた。 mid終了インデックスを実行すると、aからdに値が割り当てられていないので、0のままになっていました。この問題を解決するには==を>=に置き換えなければなりませんでした。
私はまた、あなたの作品をインデックスで修正しました。あなたは、各レベルでアレイ全体を走らせる必要はありません。また、あなたの複雑さはこのように苦しんでいます。私はその約O(n^2)と思います。 O(nlog(n))の複雑さを保つために、この再帰レベルで処理される配列の一部だけを実行すれば十分です。

固定アルゴリズムは

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

ここには、mergeSortメソッドの擬似コードがあります。それは新しい配列を作成する代わりに、既存の配列を変更している、あなたのマージ方法として

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 

：私は、あなたは、1つのまたは2つの要素のためのベースケースを無視していることがわかります。私はそれを実装するためにArrayListを使用することをお勧めします：

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