Java Insertion Sort

Question

Ci-dessous est la méthode principale appelle la méthode insertionSort mettant en plusieurs tableaux de différentes tailles. Je n'ai qu'un seul tableau dans cet exemple mais il y en a plusieurs qui seront lancés. Je n'arrive pas à comprendre comment trier arr2 comme un tri par tri. Commençant à la fin de l'arr2 en poussant jusqu'à atteindre le point correct dans le arr2 puis en regardant à nouveau le tableau non trié et en mettant le numéro suivant à la fin de arr2 puis en le triant encore et encore jusqu'à ce qu'il y ait un tri array.If vous pourriez m'aider avec ceci ce serait génial. Et oui, j'ai regardé d'autres codes mais aucun m'aider avec mon problème, j'ai passé une semaine à essayer de comprendre cela.

static void insertionSort(int[] arr) { 
    final long startTime = System.nanoTime(); // starts timer 
    System.out.println("Insertion Sort"); 
    //************** Code For Sorting *****************// 
    int[] sorted = Arrays.copyOf(arr, arr.length); // Copies unsorted array to new array 
    Arrays.sort(sorted); // sorts unsorted array for compairison later on 

    int[] arr2 = new int[arr.length]; 
    for(int h = 0; h < arr.length - 1; h++){// makes arr2 all 0's 
     arr2[h] = 0; 
    } 

    arr2[arr2.length - 1] = arr[0]; 
    for(int k = 0; k < arr.length; k++){ 
     System.out.print(arr2[k] + ", "); 
    } 
    System.out.println(); 


    while(arr2 != sorted){ 

     for(int i = 1; i < arr2.length; i++){ 
      if(arr[i] < arr2[arr2.length-1]){ 
       int last = arr2[arr2.length-1]; 
       int before = arr[i]; 
       arr2[arr2.length-1]= before; 
       arr2[arr2.length-2]= last; 

       // CANT FIGURE OUT HOW TO SORT CORRECTLY 
      } 





      for(int k = 0; k < arr.length; k++){ 
       System.out.print(arr2[k] + ", "); 
      } 
      System.out.println(); 
     } 

    } 
    for(int k = 0; k < arr.length; k++){ 
     System.out.print(arr2[k] + ", "); 
    } 
} 
public static void main(String[] args) { 
    int arr[] = {}; // Array that will be put into each sort method 
    //****************Multiple Arrays for testing*******************// 

    /* ************All Arrays Are Whole Numbers 1-100*************** 
    arr1 = Array of size 20 
*************************************************************** */ 
    int arr1[] = {6,3,20,10,11,2,9,1,19,17,4,16,8,15,18,14,5,7,12,13}; // {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20} 
//**************************************************************// 
    int arrayNumber = 1; 
    while(arrayNumber < 2){ 
     if (arrayNumber == 1){ 
      arr = arr1; 
     } 
System.out.println("Array "+ arrayNumber +" Before Sorting"); 
     for(int i = 0; i < arr.length; i++){ 
      System.out.print(arr[i] + ", "); 
     } 
     System.out.println(); 
     //************* Array put into Methods***************// 
insertionSort(arr); 
//***************************************************// 
     arrayNumber++; // Adds 1 to arrayNumber to show next array 
    } 

} 

Answer 1

au premier arr2 ne peut jamais == sorted. == signifie que deux objets ont la même adresse en mémoire. Ensuite, insérer le tri est un ensemble d'objets, et les stocker dans une collection triée, dans votre méthode insertionSort(int[] arr), au moins vous avez besoin de deux tableaux, votre arr2 est un tableau trié .mais vous avez besoin de plus d'espace, en d'autres mots, vous pouvez initialiser arr2 = new int[arr.length*2]; puis juste .and itérer arr .et insérer arr[i] en droit interjeta endroit est quand vous comparez avec arr[i]arr2[j] si arr[i]>= arr[j] && arr[i]<arr[j+1], l'indice j est le bon endroit . puis déplacer tout l'élément de arr2 entre l'index j et le dernier élément de arr2, nous avons dit arr[k], pas arr2.length-1, d'une manière primordiale, vous devez déplacer arr2[k] d'abord par une étape , tout comme arr[k+1]=arr[k]; et à partir de maintenant un objet a été inséré dans le arr2.