Fusionner les questions de mise en œuvre du tri en Java

Question

Je suis dans un cours d'algorithmes et j'apprends le tri par fusion. Notre professeur nous a recommandé d'essayer d'implémenter le pseudo code fourni dans le livre.

1. je raison de l'utilisation en tant que valeur Integer.MAX_VALUE sentinelle lorsque tri un tableau d'entiers (utilisé dans les lignes 8 & 9 dans le pseudo-code de la méthode de fusion ci-dessous)?
2. Pour la ligne 2 de la méthode de pseudo-code Merge-Sort, est-il correct de coder en Java en utilisant Math.ceil() comme je l'ai fait? (Edit: Il est en fait étage et je mis à jour mon code pour en tenir compte.)

Si vous voyez d'autres erreurs s'il vous plaît laissez-moi savoir!

Voici le pseudo code donné par le livre pour le tri par fusion.

Et, voici comment je codé en Java:

public void mergeSort(int[] arrNums, int p, int r) { 
    if (p < r) { 
     int q = (p + r)/2; 
     mergeSort(arrNums, p, q); 
     mergeSort(arrNums, q + 1, r); 
     merge(arrNums, p, q, r); 
    } 
} 

public void merge(int[] arrNums, int p, int q, int r) { 
    int nOne = q - p + 1; 
    int nTwo = r - q; 

    int[] arrLeft = new int[nOne + 1]; 
    int[] arrRight = new int[nTwo + 1]; 

    for (int i = 0; i < nOne; i++) { 
     arrLeft[i] = arrNums[p + i - 1]; 
    } 

    for (int j = 0; j < nTwo; j++) { 
     arrRight[j] = arrNums[q + j]; 
    } 

    arrLeft[nOne] = Integer.MAX_VALUE; 
    arrRight[nTwo] = Integer.MAX_VALUE; 

    // Tracks arrLeft index 
    int i = 0; 

    // Tracks arrRight index 
    int j = 0; 

    for (int k = p; k < r; k++) { 
     if (arrLeft[i] <= arrRight[j]) { 
      arrNums[k] = arrLeft[i]; 
      i++; 
     } else { 
      arrNums[k] = arrRight[j]; 
      j++; 
     } 
    } 
} 

Answer 1

La dernière boucle for dans votre méthode merge variable k doit partir p - 1:

for (int k = p - 1; k < r; k++) { 
    if (arrLeft[i] <= arrRight[j]) { 
     arrNums[k] = arrLeft[i]; 
     i++; 
    } else { 
     arrNums[k] = arrRight[j]; 
     j++; 
    } 
} 

Pseudo-code dans de nombreux manuels aime commencer l'index de tableau de 1, donc ici vous devez le soustraire par 1.

Answer 2

Je l'ai mis en œuvre il ya quelques jours, si quelqu'un va être intéressé.

private static void mergeSort(double[] arr, int start, int end){ 
    if(start < end){ 
     int mid = (start + end)/2; 
     mergeSort(arr, start, mid); 
     mergeSort(arr, mid + 1, end); 
     Merge(arr, start, mid, end); 
    } 
} 


private static void Merge(double[] arr, int start, int mid, int end){ 

    double[] leftArray = new double[mid - start + 2]; 
    double[] rightArray = new double[end - mid + 1]; 
    for(int i = start; i <= mid; i++) 
     leftArray[i - start] = arr[i]; 
    for (int i = mid + 1; i <= end; i++) 
     rightArray[i - mid - 1] = arr[i]; 

    leftArray[mid - start + 1] = Double.POSITIVE_INFINITY; 
    rightArray[end - mid] = Double.POSITIVE_INFINITY; 

    int leftIndex = 0, rightIndex = 0; 

    for (int k = start; k <= end; k++){ 
     if(leftArray[leftIndex] <= rightArray[rightIndex]) 
      arr[k] = leftArray[leftIndex++]; 
     else 
      arr[k] = rightArray[rightIndex++]; 
    } 
}