L'implémentation de Coreman MergeSort dans Java ne produit pas de sortie correcte

Question

J'essaye d'implémenter l'algorithme de Coreman MergeSort en Java. Mais ça me donne toujours une mauvaise sortie.

Avant de tri: [86, 8, 60, 9, 49, 73, 37, 59, 98, 69]

après triage: [8, 8, 9, 37, 37, 49, 49, 59, 69, 69]

Après mon code:

public class MergeSort { 
    /** 
    * @param args 
    */ 
    public static void main(String[] args) { 
     // TODO Auto-generated method stub 
     MergeSort mergeSort = new MergeSort(); 
     int [] data = mergeSort.createRandomNumberArray(); 
     mergeSort.print("Before sorting", data); 
     long startTime = System.currentTimeMillis(); 
     mergeSort.sort(data); 
     long endTime = System.currentTimeMillis(); 
     mergeSort.print("After Sorting", data); 
     mergeSort.time(startTime, endTime); 

    } 

    public void sort(int[] data) { 
     if(data == null) 
      throw new NullPointerException(); 
     if(data.length == 0 || data.length == 1) { 
      System.out.println("Size is " + data.length); 
      return; 
     } 

     int length = data.length; 
     mergeSort(data, 0, length - 1); 
    } 

    /** 
    * @param data 
    * @param first 
    * @param last 
    */ 
    private void mergeSort(int[ ] data, int first, int last) { 
     if(first < last) { 
      int middle = (first + last)/2; 
      mergeSort(data, first, middle); 
      mergeSort(data, middle + 1, last); 
      merge(data, first, middle, last); 
     } 
    } 

    private void merge(int[ ] data, int first, int middle, int end) {  
     int lSize = middle - first + 1; 
     int rSize = end - middle; 
     int [] left = new int[lSize + 1]; 
     left[lSize] = Integer.MAX_VALUE; 
     int [] right = new int[rSize + 1]; 
     right[rSize] = Integer.MAX_VALUE; 
     for(int i = 0; i < lSize; i++) { 
      left[i] = data[first + i]; 
     } 

     for(int j = 0; j < rSize; j++) { 
      right[j] = data[middle + j + 1]; 
     } 

     print("Left: ", left); 
     print("Right: ", right); 

     int lIndex = 0; 
     int rIndex = 0; 

     for(int k = first; k < end; k++) { 
      if(left[lIndex] <= right[rIndex]) { 
       data[k] = left[lIndex]; 
       lIndex++; 
      } else { 
       data[k] = right[rIndex]; 
       rIndex++; 
      } 
     } 
    } 


    public void print(String message, int [] array) { 
     System.out.println(message + " : " + Arrays.toString(array)); 
    } 

    public int [] createRandomNumberArray() { 
     int [] data = new int[] {86,8,60,9,49,73,37,59,98,69} ; 
     /*int [] data = new int[SIZE]; 
     for(int i = 0; i < SIZE; i++) { 
      data[i] = RANDOM.nextInt(RANGE); 
     }*/ 
     return data; 
    } 

    public long time(long start, long end) { 
     long time = end - start; 
     System.out.println("Time taken in sorting ==> " + time); 
     return time; 
    } 

} 

J'ai essayé d'imprimer des valeurs et déboguer le code, mais je ne suis pas en mesure de savoir ce qui ne va pas ici. S'il vous plaît suggérer ce qui ne va pas ici.

Answer 1

for(int k = first; k < **=**end; k++) { 
       if(left[lIndex] <= right[rIndex]) { 
        data[k] = left[lIndex]; 
        lIndex++; 
       } else { 
        data[k] = right[rIndex]; 
        rIndex++; 
       } 
      }