Insertion sort vs. inserimento Ordina vs binario insertion sort

Question

Ho un paio di domande riguardanti diverse implementazioni di insertion sort.

Esecuzione 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;
    }
}

Realizzazione 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;
}

Ecco la mia prima domanda: si dovrebbe pensare che la prima versione dovrebbe essere un po 'più veloce che la seconda versione (a causa di incarichi minori), ma non è (o almeno la differenza è trascurabile). Ma perché?

In secondo luogo, mi chiedevo che Arrays.sort di Java () utilizza anche il secondo approccio (forse a causa del riutilizzo del codice perché il metodo di swap viene utilizzato in luoghi diversi, forse perché è più facile da capire).

Attuazione 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;
        }
    }
}

È il binario inserimento sorta di alcuna utilità pratica, o è più di una cosa teorica? Su piccoli array, gli altri approcci sono molto più veloci, e su array più grandi Mergesort / Quicksort ha una prestazione molto migliore.

Answer 1

1. eliminare falsa dichiarazione
2. Il numero di confronti nei primi due è 1/2 * n (n-1), ad esclusione di quelli per i loop esterni.
3. Nessuno di questi programmi ha molto senso per il lavoro vero e proprio come sono, perché non fanno uso delle informazioni a loro disposizione. Ad esempio, è facile aggiungere un controllo per il ciclo interno per verificare se sono state effettuate delle swap: se poi non l'array è ordinato, e si può finire, forse risparmiando maggior parte del lavoro. In pratica, questo tipo di esame possono dominare il caso medio.

Postscript Perse la questione su Java: capisco che tipo di Java è un algoritmo piuttosto complessa, che utilizza un sacco di casi particolari, come ad esempio i casi di smistamento specializzati per piccoli array, e l'utilizzo di Quicksort per fare il suo sollevamento di carichi pesanti.