Insertionsort vs. Insertionsort vs. BinaryInsertionsort

Question

Eu tenho algumas perguntas sobre diferentes implementações do tipo de inserção.

Implementação 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;
    }
}

Implementação 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;
}

Aqui está minha primeira pergunta: deve -se pensar que a primeira versão deve ser um pouco mais rápida que a segunda versão (devido a tarefas menores), mas não é (ou pelo menos a diferença é insignificante). Mas por que?

Segundo, eu estava me perguntando que o método de Java's Arrays.sort () também use a segunda abordagem (talvez por causa da reutilização do código porque o método de troca é usado em lugares diferentes, talvez porque seja mais fácil de entender).

Implementação 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;
        }
    }
}

A inserção binária é um tipo de uso prático ou é mais uma coisa teórica? Em pequenas matrizes, as outras abordagens são muito mais rápidas e, em matrizes maiores, mesclar mescle/Quicksort tem um desempenho muito melhor.

Answer 1

1. Excluir uma reivindicação falsa
2. O número de comparações nos dois primeiros é de 1/2*n (n-1), excluindo os dos loops externos.
3. Nenhum desses programas faz muito sentido para o trabalho real, porque não utilizam as informações à sua disposição. Por exemplo, é fácil adicionar uma verificação ao loop interno para ver se algum swaps foi feito: se não, a matriz é classificada e você pode terminar, talvez salvando a maior parte do trabalho. Na prática, esses tipos de consideração podem dominar o caso médio.

PostScriptPerdi a pergunta sobre Java: entendo que o tipo de Java é um algoritmo bastante complexo, que usa muitos casos especiais, como casos de classificação especializados para pequenas matrizes e usando o Quicksort para fazer seu levantamento pesado.