Débogage : Mergesort

Question

J'essaie d'implémenter un tri par fusion en Java. J'ai revu mon code plusieurs fois dans ma tête et j'ai l'impression qu'il devrait fonctionner, mais il est évident que je fais quelque chose de mal. Voici le code

    public static void mergeSort(int[] input, int start, int end) {
        if (end - start < 2)
            return;

        int mid = (start + end) / 2;
        mergeSort(input, start, mid);
        mergeSort(input, mid + 1, end);
        merge(input, start, mid, end);
    }

    public static void merge(int[] input, int start, int mid, int end) {
        if (input[mid - 1] <= input[mid])
            return;

        int i = start;
        int j = mid;
        int tempIndex = 0;
        int[] temp = new int[end - start]; //combined size of both arrays being merged

        /*if i is >= mid, then that means the left portion of the array is done being sorted
          and vice versa if j >= end. Once this happens, we should be able to
          just copy the remaining elements into the temp array 
        */
        while (i < mid && j < end) {
            temp[tempIndex++] = (input[i] <= input[j]) ? input[i++] : input[j++];
        }

        //Copying left over elements in left portion
        while (i < mid)
            temp[tempIndex++] = input[i++];

        //Copying left over elements in right portion
        while (j < end)
            temp[tempIndex++] = input[j++];

        //Copy the sorted temp array into the original array
        //This is where I think I must be messing up
        for (int k = 0; k < temp.length; k++) {
            input[start + k] = temp[k];    
        }
     }

Je pense que c'est parce que je ne recopie pas correctement le tableau temporaire avec les éléments triés dans le tableau original, mais je ne suis pas sûr. J'ai écrit des commentaires sur mon code pour expliquer ma logique.

Answer 1

Jetez un coup d'œil aux changements suivants :

1. Calculer le milieu

   int mid = start + (end - start) / 2 ;

2. Assigner correctement les pointeurs i,j.

   int i = start ; int j = milieu+1 ;

3. Taille correcte du tableau temporaire.

   int [] temp = new int [end-start+1] ;

4. Correction de la condition des boucles while dans le code.

    class Solution{
   
    public static void mergeSort(int[] input, int start, int end) 
    {
        if (end == start ) return;
   
        int mid = start + (end - start) / 2;
        mergeSort(input, start, mid);
        mergeSort(input, mid+1, end);
        merge(input, start, mid, end);
    }
   
     public static void merge(int[] input, int start, int mid, int end) {
        // No Need of the under mentioned instruction
        // if(input[mid-1] <= input[mid]) return;
   
        int i = start;
        int j = mid+1;
        int tempIndex = 0;
        int [] temp = new int[end-start+1]; //combined size of both arrays being merged
   
        /*if i is >= mid, then that means the left portion of the array is done being sorted and vice versa if j >= end. Once this happens, we should be able to just copy the remaining elements into the temp array */
   
        while(i <= mid && j <= end){
            temp[tempIndex++] = (input[i] <= input[j]) ? input[i++] : input[j++];
        }
   
        //Copying left over elements in left portion
        while(i <= mid)
            temp[tempIndex++] = input[i++];
   
        //Copying left over elements in right portion
        while(j <= end)
            temp[tempIndex++] = input[j++];
   
        //Copy the sorted temp array into the original array
        //This is where I think I must be messing up
        for(int k = 0; k < temp.length; k++){
            input[start+k] = temp[k];    
        }
     }
   
    public static void main(String[] args){
        int[] input = {9,4,6,8,5,7,0,2};
        mergeSort(input,0,7);
   
        for(int i : input)
            System.out.println(i);    
    }
   
    }