Ordenar la inserción frente a la inserción Ordenar vs. Binario ordenación por inserción

Question

Tengo un par de preguntas sobre diferentes implementaciones de ordenación por inserción.

Aplicación 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;
    }
}

Aplicación 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;
}

Esta es mi primera pregunta: ¿Hay que pensar que la primera versión debería ser un poco más rápido que la segunda versión (a causa de las asignaciones menores) pero no es (o al menos la diferencia es insignificante). Pero ¿por qué?

En segundo lugar, me preguntaba que Arrays.sort de Java () método también utiliza el segundo método (tal vez debido a la reutilización de código debido a que el método de intercambio se utiliza en diferentes lugares, tal vez porque es más fácil de entender).

Implementación 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;
        }
    }
}

es el tipo de inserción binaria de cualquier uso práctico, o es más de una cosa teórica? En arreglos pequeños, los otros enfoques son mucho más rápidos, y en matrices más grandes mergesort / quicksort tiene un rendimiento mucho mejor.

Answer 1

1. falso reclamo de eliminación
2. El número de comparaciones en los dos primeros es 1/2 * n (n-1), excluyendo aquellos para los bucles exteriores.
3. Ninguno de estos programas tiene mucho sentido para el trabajo real, tal y como están, porque no hacen uso de la información a su disposición. Por ejemplo, es fácil añadir un cheque para el bucle interno para ver si se ha realizado algún permutas: si no, entonces la matriz está ordenada, y se puede terminar, tal vez salvar la mayor parte del trabajo. En la práctica, este tipo de examen pueden dominar el caso promedio.

Postscript Se perdió la pregunta acerca de Java: entiendo ese tipo de Java es un algoritmo bastante complejo, que utiliza una gran cantidad de casos especiales, como los casos de clasificación especializados para pequeños arreglos, y el uso de la clasificación rápida de hacer su trabajo pesado.