InsertionSort vs InsertionSort vs BinaryInsertionSort

Question

J'ai quelques questions concernant différentes implémentations de tri d'insertion.

Application 1:

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

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

     a[j + 1] = key; 
    } 
} 

Mise en œuvre 2:

public static void insertionSort(int[] a) { 
    for (int i = 1; i < a.length; ++i) { 
     for (int j = i; j > 0 && a[j - 1] > a[j]; --j) { 
      swap(a, j, j - 1); 
     } 
    } 
} 

private static void swap(int[] a, int i, int j) { 
    int tmp = a[i]; 

    a[i] = a[j]; 
    a[j] = tmp; 
} 

Voilà ma première question: Il faut penser que la première version devrait être un peu plus rapide que la deuxième version (en raison des affectations moins) mais ce n'est pas (ou du moins la différence c'est négligeable). Mais pourquoi? Deuxièmement, je me demandais que la méthode Arrays.sort() de Java utilise aussi la seconde approche (peut-être à cause de la réutilisation du code parce que la méthode swap est utilisée à différents endroits, peut-être parce qu'elle est plus facile à comprendre).

Mise en œuvre 3 (binaryInsertionSort):

public static void binaryInsertionSort(int[] a) { 
    for (int i = 1; i < a.length; ++i) { 
     int pos   = Arrays.binarySearch(a, 0, i, a[i]); 
     int insertionPoint = (pos >= 0) ? pos : -pos - 1; 

     if (insertionPoint < i) { 
      int key = a[i]; 

      // for (int j = i; i > insertionPoint; --i) { 
      //  a[j] = a[j - 1]; 
      // } 
      System.arraycopy(a, insertionPoint, a, insertionPoint + 1, i - insertionPoint); 

      a[insertionPoint] = key; 
     } 
    } 
} 

est le genre d'insertion binaire d'une utilisation pratique, ou est-il plus d'une chose théorique? Sur les petits réseaux, les autres approches sont beaucoup plus rapides, et sur les réseaux plus grands, mergesort/quicksort a de meilleures performances.

Answer 1

1. Supprimer fausse revendication
2. Le nombre de comparaisons dans les deux premiers est égal à 1/2 * n (n-1), l'exclusion de ceux pour les boucles externes.
3. Aucun de ces programmes n'a de sens pour le vrai travail tel quel, car ils n'utilisent pas les informations dont ils disposent. Par exemple, il est facile d'ajouter une vérification à la boucle interne pour voir si des swaps ont été faits: si ce n'est pas le cas, le tableau est trié, et vous pouvez terminer, peut-être sauver la majeure partie du travail. En pratique, ce genre de considération peut dominer le cas moyen.

Postscript Maladroit question sur Java: Je comprends que le genre de Java est un algorithme assez complexe, qui utilise beaucoup de cas particuliers, comme les cas de tri spécialisé pour les petits réseaux, et en utilisant quicksort pour faire son levage de charges lourdes.