InsertionSort contre InsertionSort vs BinaryInsertionSort

Question

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

Mise en œuvre 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 (à cause des affectations moins), mais il n'est pas (ou du moins la différence qu'il est négligeable). Mais pourquoi?

Deuxièmement, je me demandais cette méthode Arrays.sort () Java utilise également la seconde approche (peut-être en raison de la réutilisation du code, car la méthode d'échange est utilisé dans des endroits différents, peut-être parce qu'il est plus facile à comprendre).

Mise en oeuvre 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 type 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 mergesort / quicksort plus grands tableaux a une bien meilleure performance.

Answer 1

1. supprimer fausse déclaration
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 font beaucoup de sens pour le travail réel qu'ils sont, parce qu'ils ne font pas usage de l'information à leur disposition. Par exemple, il est facile d'ajouter un chèque à la boucle interne pour voir si des swaps ont été faites: si pas alors le tableau est triée, et vous pouvez finir, peut-être sauver la plupart des travaux. Dans la pratique, ce genre de considération peuvent dominer le cas moyen.

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