Java - tri d'insertion binaire, dépannage

J'ai une tâche où j'ai besoin de trier un tableau en utilisant le tri par insertion binaire. Ce est la solution que je suis venu avec, mais il est trop lent:Java - tri d'insertion binaire, dépannage

public static void binaryInsertionSort(int[] a) { 
    int ins, i, j; 
    int tmp; 
    for (i = 1; i < a.length; i++) { 
     ins = BinarySearch (a, 0, i, a[i]); 
      if(ins < i) { 
       tmp = a[i]; 
       for (j = i - 1; j >= ins; j--) 
        a[j+1] = a[j]; 
       a[ins] = tmp; 
      } 
    } 
} 

private static int BinarySearch(int[] a, int low, int high, int key) { 

    int mid; 
    if (low == high) 
     return low; 
    mid = low + ((high - low)/2); 
    if (key > a[mid]) 
     return BinarySearch (a, mid + 1, high, key); 
    else if (key < a[mid]) 
     return BinarySearch (a, low, mid, key); 
    return mid; 

}

m'a recommandé d'utiliser la méthode System.arraycopy que je l'ai essayé, mais je ne comprends pas pourquoi il ne fonctionne pas:

public static void binaryInsertionSort(int[] a) { 
    int ins, i; 
    int tmp = a[i]; 
    for (i = 1; i < a.length; i++) { 
     ins = binarySearch (a, 0, i, a[i]); 
      if(ins < i){ 
       System.arraycopy(a, ins, a, ins + 1, i - ins); 
       a[ins] = tmp; 
      } 
    } 
} 

private static int binarySearch(int[] a, int low, int high, int key) { 
    int mid; 
    if (low == high) 
     return low; 
    mid = low + ((high - low)/2); 
    if (key > a[mid]) 
     return binarySearch (a, mid + 1, high, key); 
    else if (key < a[mid]) 
     return binarySearch (a, low, mid, key); 
    return mid; 
}

Toute aide est utile.

Source

2017-02-19 elMatador

Décrivez ce qui se passe lorsque vous exécutez ** ** votre code Mettez un ** complet. ** [mcve] qui nous montre avec quelles données vous travaillez, et comment les résultats attendus/réels ressemblent – GhostCat

Le code original que vous avez écrit dans la première fois me va bien, je ne suis pas sûr de ce que vous vouliez dire par son trop lent. Le tri par insertion binaire prend la complexité du temps O (n^2) à la fin. r deuxième travail de mise en œuvre? Même si vous faites fonctionner votre deuxième implémentation en utilisant system.arraycopy, je ne crois pas que cela rendra votre programme très rapide. Pour un algorithme de tri rapide, utilisez l'un des algorithmes O (nlogn). –

Ma question était de faire fonctionner le deuxième code. Oui, même si le code initial fonctionne, la méthode System.arraycopy est environ 4 fois plus rapide que la méthode originale)) – elMatador

Eh bien, en attendant, la réponse était plus facile que je ne le pensais. J'ai initialisé la variable locale au mauvais endroit. Au lieu de:

La manière correcte est:

public static void binaryInsertionSort(int[] a) { 
    int ins, i; 
     for (i = 1; i < a.length; i++) { 
      **int tmp = a[i];** 
      ins = binarySearch (a, 0, i, a[i]); 
       if(ins < i){ 
        System.arraycopy(a, ins, a, ins + 1, i - ins); 
        a[ins] = tmp; 
       } 
    } 
}

Et cela fonctionne (:

Source

2017-02-19 11:46:21 elMatador

Java - tri d'insertion binaire, dépannage

Répondre

Questions connexes