実際にソートされていないMergesort

Question

私のパラメータには配列だけを使ってmergesortを実装する必要があります。私はそれがそれを分割して再組み立てしているのを見ることができますが、そうしている間にそれを実際にソートしているわけではありません。私はそれがどこで/どのように物事を呼び出すかと関係していると確信しています。私はそれを修正することができますので、正しいデータをピックアップしていない場所を指摘することができますか？

public static void mergesort(Comparable[] a) { 
    a = mergeSort(a); 
} 

public static Comparable[] mergeSort(Comparable[] a) { 
    Comparable[] first, second; 
    int length1 = a.length/2; 
    int length2 = a.length - length1; 

    first = Arrays.copyOfRange(a, 0, length1); 
    second = Arrays.copyOfRange(a, length1, a.length); 

    if(length1 > 0 && length2 > 0) { 
     first = mergeSort(first); 
     System.out.print("First: "); 
     show(first); 
     second = mergeSort(second); 
     System.out.print("Second: "); 
     show(second); 
     a = merge(first, second); 
     System.out.print("\nAfter: "); 
     show(a); 
    } 
    return a; 
} 

public static Comparable[] merge(Comparable[] a, Comparable[] b) { 
    Comparable[] temp = new Comparable[a.length + b.length]; 
    int aFirst = 0, aLast = a.length - 1; 
    int bFirst = 0, bLast = b.length - 1; 
    int index = aFirst; 

    while(aFirst <= aLast && bFirst <= bLast) { 
     if(a[aFirst].compareTo(b[bFirst]) < 0) { 
      temp[index] = a[aFirst++]; 
     } else { 
      temp[index] = b[bFirst++]; 
     } 
     index++; 
    } 

    while(aFirst <= aLast) { 
     temp[index] = a[aFirst++]; 
     index++; 
    } 

    while(bFirst <= bLast) { 
      temp[index] = b[bFirst++]; 
      index++; 
    } 
    return temp; 
} 

追加する編集：ここで私は（とされ、私は変更することはできません）で働いていmainメソッドからの抜粋です。

String[] b = {"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"}; 
    mergesort(b); 
    assert isSorted(b); 
    show(b); 

Answer 1

これらの二つの呼び出し：新しいアレイに

mergesort(first); 
mergesort(second); 

ソート配列firstとsecondができますが、それらのソート配列を無視します。あなたのコードは次のようになります。

first = mergeSort(first); 
second = mergesort(second); 

---

実際の問題は、あなたが同様の名前（mergesortとmergeSort）が、非常に異なる意図した動作をする2つのメソッドを持っていること、である。これらの方法の一つは、その入力とリターンをソートするためにしようとしますもう一方はソートされた結果を返さないため、入力を変更する必要があります。

どちらの方法にもメリットがあります。しかし、あなたの現在のコードはこれらをアプローチに混在させ、それは間違っています。

---

何あなたの現在のコードは、バック引数配列に並べ替え要素を格納している欠落しています。

public static void mergesort(Comparable[] a) { 
    Comparable[] sorted = mergeSort(a); 
    System.arrayCopy(sorted, 0, a, 0, a.length); 
} 

との：あなたのヘルパーメソッドがない場合は、あなたのクラスの外から呼ばれるように、彼らにこのようなprivateを作ります：

private static Comparable[] mergeSort(Comparable[] a) { 
    ... 
} 

private static Comparable[] merge(Comparable[] a, Comparable[] b) { 
    ... 
} 

に名前を変更することもできます。

究極の目標は、コードをできるだけ読みやすくし、コードの読者にあなたの意図を示すことです。