Fusionner trier les questions d'implémentation en Java

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. Ai-je raison d'utiliser Integer.MAX_VALUE comme valeur sentinelle lorsque tri d'un tableau d'entiers (utilisé dans les lignes 8 et 9 de la fusion la méthode du pseudo-code ci-dessous)?
  2. Pour la ligne 2 de la méthode de pseudo-code Merge-Sort, est-il correct de coder cela en Java en utilisant les mathématiques.ceil () comme je l'ai fait? (Edit: C'est en fait le sol et j'ai mis à jour mon code pour refléter cela.)

Si vous voyez d'autres erreurs, faites-le moi savoir!

Voici le pseudo code que le livre donne pour le tri par fusion. algorithme de tri de fusion partie 1

algorithme de tri de fusion partie 2

Et, voici comment je l'ai 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++;
        }
    }
}
Author: Nishant, 2017-04-02
Source

2 answers

La dernière boucle for dans votre méthode merge, la variable k devrait commencer à partir de 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++;
    }
}

Le pseudo-code dans de nombreux livres de texte aime démarrer l'index de tableau à partir de 1, donc ici vous devez le soustraire par 1.

 1
Author: shizhz, 2017-04-02 00:17:40

Je l'ai implémenté il y a quelques jours, si quelqu'un sera 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++];
    }   
}
 0
Author: sheldonzy, 2017-08-20 13:53:55