反復Javaマージソート

Question

課題のマージソートの反復バージョンを作成しようとしています。私は、WebサイトからMergeソートメソッドを取得し、配列をマージするはずのメソッドに取り組みました。しかし、私はIndexOutOfBounds例外を得ています。

私はこれを複数の時間作業していますが、エラーが見つかりません。誰かが私にこれを解決する方法を見つけるのを助けることができますか？

これまでのところ、私はこれがあります。

public static void MergeSort(int[] array) { 
    int current; 
    int leftStart; 
    int arraySize = array.length - 1; 
    for (current = 1; current <= arraySize; current = 2 * current) { 
     for (leftStart = 0; leftStart <= arraySize; leftStart += 2 * current) { 

      int mid = leftStart + current - 1; 
      int right = getMin(leftStart + 2 * current - 1, arraySize); 

      mergeArray(array, leftStart, mid, right); 
     } 

    } 

} 

public static void mergeArray(int[] array, int left, int mid, int right) { 

    int leftArraySize = mid - left + 1; 
    int rightArraySize = right - mid; 

    int[] leftArray = new int[leftArraySize]; 
    int[] rightArray = new int[rightArraySize]; 

    for (int i = 0; i < leftArraySize; i++) 
     leftArray[i] = array[left + i]; 

    for (int i = 0; i < rightArraySize; i++) 
     rightArray[i] = array[mid + 1 + i]; 

    int leftPtr = 0; 
    int rightPtr = 0; 
    int tempPtr = leftPtr; 

    while (leftPtr < leftArraySize && rightPtr < rightArraySize) { 

     if (leftArray[leftPtr] <= rightArray[rightPtr]) 
      array[tempPtr++] = leftArray[leftPtr++]; 

     else 
      array[tempPtr++] = rightArray[rightPtr++]; 
    } 

    while (leftPtr <= left) 
     array[tempPtr++] = leftArray[leftPtr++]; 

    while (rightPtr < right) 
     array[tempPtr++] = rightArray[rightPtr++]; 

} 

public static int getMin(int left, int right) { 
    if (left <= right) { 
     return left; 
    } else { 
     return right; 
    } 
} 

ヘルプの任意の並べ替えが高く評価されます！

ありがとうございます！

Answer 1

このコードを正常に実行してみてください...

array[tempPtr++] = leftArray[leftPtr++]; 

は、アレイ内で増加しない

array[tempPtr] = leftArray [leftPtr]; 
     leftPtr++; 

を交換して最終的なコード：mergeArray()方法でのみ小さなミス をを比較し私のコードを取得します。

public static void MergeSort(int[] array) { 
int current; 
int leftStart; 
int arraySize = array.length; 
for (current = 1; current <= arraySize-1; current = 2 * current) { 
for (leftStart = 0; leftStart < arraySize-1; leftStart += 2 * current) { 

    int mid = leftStart + current - 1; 
    int right = getMin(leftStart + 2 * current - 1, arraySize-1); 

    mergeArray(array, leftStart, mid, right); 
}}} 

static void printArray(int A[]) 
{ 
int i; 
    for (i=0; i < A.length; i++) 
    System.out.println(A[i]); 
    } 

static void mergeArray(int array[], int left, int mid, int right) 
    { 
    int leftArraySize = mid - left + 1; 
int rightArraySize = right - mid; 

     int[] leftArray = new int[leftArraySize]; 
int[] rightArray = new int[rightArraySize]; 

for (int i = 0; i < leftArraySize ; i++) 
    leftArray [i] = array[left + i]; 
for (int j = 0; j < rightArraySize; j++) 
    rightArray[j] = array[mid + 1+ j]; 

    int leftPtr = 0; 
    int rightPtr = 0; 
    int tempPtr = left; 
while (leftPtr < leftArraySize && rightPtr < rightArraySize) 
{ 
    if (leftArray [leftPtr ] <= rightArray[rightPtr ]) 
    { 
     array[tempPtr] = leftArray [leftPtr]; 
     leftPtr++; 
    } 
    else 
    { 
     array[tempPtr] = rightArray[rightPtr]; 
     rightPtr++; 
    } 
    tempPtr++; 
} 

while (leftPtr < leftArraySize) 
{ 
    array[tempPtr++] = leftArray [leftPtr++]; 

    leftPtr++; 
    tempPtr++; 
} 

while (rightPtr < rightArraySize) 
{ 
    array[tempPtr++] = rightArray[rightPtr++]; 

    rightPtr++; 
    tempPtr++; 
} } 

    public static int getMin(int left, int right) { 
    if (left <= right) { 
return left; 
} else { 
    return right; 
}} 

Answer 2

マージソートアルゴリズムは、古典的な除算および征服アルゴリズムです。

1. 分割小さなサブ問題再帰呼び出しを介し
2. 征服に問題。
3. 元の問題のために1

にマージのための擬似コードをサブ問題の解決策を組み合わせる：

C = output[length = n] 
A = 1st sorted array[n/2] 
B = 2st sorted array[n/2] 
i = 1 
j = 1 
for k = 1 to n 
    if A[i] < B[j] 
     C[k] = A[i] 
     i++ 
    else B[j]<A[i] 
     C[k] = B[j] 
     j++ 
end (ignores end cases) 

だからあなたのソースコードの問題は、この行です：

array[tempPtr++] = leftArray[leftPtr++]; 

変更してください擬似コードの論理へ：

if (leftArray [leftPtr ] <= rightArray[rightPtr ]) 
{ 
    array[tempPtr] = leftArray [leftPtr]; 
    leftPtr++; 
} 
else 
{ 
    array[tempPtr] = rightArray[rightPtr]; 
    rightPtr++; 
}