défaut de l'algorithme de tri d'insertion dans le code Java

Question

Je vais à travers quelques-uns des algorithmes de tri communs et ont écrit ceci:

code:

public void insertionSort() { 
    int key; 
    int i; 
    for (int j = 1; j < this.a.length; j++) { 
     key = a[j]; 
     i = j; 

     while (i > 0 && a[i-1] > key) { 
      a[i] = a[i-1]; 
      i = i - 1; 
     } 
     a[i] = key; 
    } 
} 

Résultat:

jan@janspc:~/Dropbox/programming/java/algorithms$ javac sort.java 
jan@janspc:~/Dropbox/programming/java/algorithms$ java Test 
49, 68, 60, 14, 70, 8, 83, 96, 29, 7, 92, 35, 17, 84, 31, 62, 48, 95, 16, 22, 31, 97, 72, 55, 88, 63, 1, 63, 96, 32, 74, 15, 92, 77, 50, 13, 12, 36, 90, 93, 20, 15, 67, 88, 23, 31, 95, 90, 86, 65, 35, 27, 60, 4, 90, 11, 22, 97, 65, 88, 23, 1, 25, 21, 9, 81, 87, 56, 2, 4, 63, 52, 55, 86, 62, 30, 55, 64, 19, 10, 45, 92, 87, 43, 39, 95, 20, 43, 3, 30, 74, 64, 4, 90, 91, 93, 94, 44, 87, 21, 

49, 1, 1, 2, 3, 4, 4, 4, 7, 8, 9, 10, 11, 12, 13, 14, 15, 15, 16, 17, 19, 20, 20, 21, 21, 22, 22, 23, 23, 25, 27, 29, 30, 30, 31, 31, 31, 32, 35, 35, 36, 39, 43, 43, 44, 45, 48, 50, 52, 55, 55, 55, 56, 60, 60, 62, 62, 63, 63, 63, 64, 64, 65, 65, 67, 68, 70, 72, 74, 74, 77, 81, 83, 84, 86, 86, 87, 87, 87, 88, 88, 88, 90, 90, 90, 90, 91, 92, 92, 92, 93, 93, 94, 95, 95, 95, 96, 96, 97, 97, 

Execution took: 110628 nano sek? 

Comme vous pouvez le voir lors des tests, la première valeur n'est pas affectée par le tri. Quel est le problème avec mon algorithme?

Answer 1

Lors de la première itération, la boucle while ne s'exécute pas, car i < 0. Lors de l'itération suivante, la boucle while ne s'exécute pas car i == 0.

Vous devriez probablement utiliser while (i >= 0 && a[i] > key) (non testé si)

Answer 2

Vous devez >= ici:

while (i >= 0 && a[i] > key){ 

Sans ce changement, il compare jamais les éléments suivants contre le premier.

Answer 3

while (i > 0 && a[i] > key){ devrait être while (i >= 0 && a[i] > key){

chance ultime ...

Answer 4

code corrigé:

public void insertionSort() { 
    int key; 
    int i; 
    for (int j = 1; j < this.a.length; j++) { 
     key = a[j]; 
     i = j; 

     while (i > 0 && a[i-1] > key) { 
      a[i] = a[i-1]; 
      i = i - 1; 
     } 
     a[i] = key; 
    } 
} 

Answer 5

est inférieure à la pseudo-code du type d'insertion (tiré de CLR "Introduction to al livre des gorithmes).

Insertion-tri (A)

for (j = 2 à a.length)

key = A[j]> 
i = j-1 
while i>0 && A[i]>key 
    A[i+1] = A[i] 
    i = i-1 
A[i+1] = key 

Votre code est presque similaire à ci-dessus pseudo-code. Tout ce que vous avez besoin est de changer l'initialisation de int j=0-int j=1 dans for boucle:

for (int j = 1; j < this.a.length; j++) { 
    key = a[j]; 
    i = j - 1; 

    while (i > 0 && a[i] > key) { 
     a[i + 1] = a[i]; 
     i = i - 1; 
    } 
    a[i+1] = key; 
} 

Answer 6

En Insertion Sort nous devons vérifier chaque élément de tableau et de comparer avec d'autres éléments obtenir des résultats plus précis.Le problème dans votre code dans while nous avons besoin de la ligne

while (i >= 0 && a[i] > key) 

Answer 7

Voici une autre mise en œuvre du tri par insertion dans java

public class InsertionSort {

static int intArray[] = { 1000, 1, 100, 101, 15 }; 

public static void doSort() { 
    for (int outer = 1; outer < intArray.length; outer++) { 
     for(int inner=outer;inner>0; inner--){ 
      if(intArray[inner]<intArray[inner-1]){ 
       int temp=intArray[inner]; 
       intArray[inner]=intArray[inner-1]; 
       intArray[inner-1]=temp; 
       continue; 
      } 
     } 
    } 
} 

public static void printArray() { 
    for (int i = 0; i < intArray.length; i++) { 
     System.out.print(" " + intArray[i]); 
    } 
} 

public static void main(String args[]) { 
    System.out.print("Array Before Sorting->"); 
    printArray(); 
    doSort(); 
    System.out.print("\nArray After Sorting ->"); 
    printArray(); 
} 

}

Explication détaillée du code et/ou de l'algortithm peut être vu à - http://www.javabrahman.com/algorithms-in-java/insertion-sort-in-java/

Answer 8

ici est très facile de mise en œuvre tri par insertion

package insertion_sort; 

public class insertion_sort { 
    public static void main(String ar[]) { 
     int[] a = {24, 13, 9, 64, 7, 23, 34, 47, 87, 9, 37, 1992}; 
     insertion(a,12); 
    } 

    public static void insertion(int[] a, int n) { 
     for (int i = 1; i <= n - 1; i++) { 
      int value = a[i]; 
      int hole = i; 
      while (hole > 0 && a[hole - 1] > value) { 
       a[hole] = a[hole - 1]; 
       hole = hole - 1;  
      } 
      a[hole] = value; 
     } 
     print(a);  
    } 

    public static void print(int[] A) {  
     for (int i = 0; i < A.length; i++) {  
      System.out.print(A[i] + " ");  
     }  
     System.out.println(); 
    }  
} 

Answer 9

public static int[] insrtSort(int array[]){ 

    for(int i=0 ; i<array.length-1;i++){ 
     int value=array[i+1],k=i; 

     while(value<array[k]){ 

      array[k+1]=array[k]; 
      if(k!=0) 
      k--; 
      else 
       array[0]=value; 
     } 
     if(k!=0) 
     array[k+1]=value; 
    } 
    return array; 
    } 

Answer 10

C'est le même code mais comme une méthode qui peut être transmis une série de ints pour trier.

public static int[] insertionSort(int[] array) { 
    int key; 
    int i; 


    for (int j = 1; j < array.length; j++) { 
     key = array[j]; 
     i = j; 

     while (i > 0 && array[i-1] < key) { 
      array[i] = array[i-1]; 
      i = i - 1; 
     } 
     array[i] = key; 
    } 
    return array; 
}