Revisione e sperimentazione dei metodi di smistamento. Parte I

L'altro giorno, nei commenti su VKontakte, ho litigato con uno degli altri studenti del progetto. L'essenza della disputa era "chi vincerà" - un metodo sort()da una classe java.util.Arrayso implementazioni autoprodotte di semplici algoritmi: bolla , inserimento , selezione , shell (algoritmo Shell). Per alcuni, la risposta a questa domanda può essere ovvia, ma da quando è sorta la controversia, nonostante il fatto che ciascuna parte avesse “fonti rispettate” a favore del proprio punto di vista, si è deciso di condurre uno studio, estendendo la materia grigia in il processo, implementando vari algoritmi. TL;DR: java.util.Arrays.sort() è incondizionatamente leader su array di 100.000 elementi o più; con dimensioni inferiori, il metodo Shell a volte può competere con lui. Il resto degli algoritmi considerati sono completamente vuoti e possono essere utili solo in alcune condizioni esotiche. Ora diamo un'occhiata a come vengono ordinati gli array nei nostri super-dispositivi in ​​silicio.

Ordinamento della selezione. Ordinamento per selezione

Cominciamo con il metodo più semplice e ovvio. L'essenza di ciò ce lo dimostra perfettamente Robert Sedgwick nella sua video conferenza su Coursera (citerò l'animazione da lì che ho compresso male in una gif): Visualizza Correndo attraverso l'array dal primo elemento, ad ogni passo noi cerchiamo l'elemento minimo sul lato destro, con il quale scambiamo quello attuale. Di conseguenza, riserviamo la versione finale del nostro array in forma ordinata. Ecco il codice che implementa questo algoritmo in Java:

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

L'analisi dell'algoritmo mostra che è necessario setacciare il resto dell'array ad ogni passaggio, ovvero avremo bisogno esattamente di N + (N-1) + (N-2) + ... + 1 = N^ 2/2 confronti. Pertanto, la complessità dell'algoritmo è O(N^2). Cosa significa questo? Ciò significa che aumentando il numero di elementi dell'array (N) di 2 volte, aumenteremo il tempo di esecuzione dell'algoritmo non di 2, ma di 2^2 = 4 volte. Aumentando N di 10 volte, aumenteremo il tempo di funzionamento di 100 volte e così via. Sul mio laptop del 2012 con un processore Core i3 con Ubuntu 14.4, ho ottenuto il seguente tempo di attività:

Ordinamento di inserimento. Ordinamento di inserimento

Qui l’idea è leggermente diversa. Ancora una volta, passiamo all'animazione del Dottor Sedgwick: Guarda Ciò che ci aspetta non è stato nemmeno visto da noi, e tutto ciò che lasciamo dietro rimane sempre in ordine. Il punto è che “riportiamo” ogni nuovo elemento dell'array originale all'inizio finché non “poggia” su un elemento più piccolo. Quindi, abbiamo ancora N passaggi (per ciascun elemento dell'array originale), ma in ogni passaggio, nella maggior parte dei casi, non guardiamo l'intero resto, ma solo una parte. Otterremo cioè l'opzione 1 + (N-1) + (N-2) + … + N = N^2/2 solo se dobbiamo riportare ogni elemento successivo all'inizio, cioè nel caso dell'array di input ordinato “al contrario” (sfortunato, sfortunato). Nel caso di un array già ordinato (che fortuna) ci sarà un omaggio completo: ad ogni passaggio viene effettuato un solo confronto e lasciando l'elemento al suo posto, cioè l'algoritmo funzionerà in un tempo proporzionale a N. La complessità dell'algoritmo sarà determinato dal caso teorico peggiore, ovvero O(N^2). In media, il tempo di funzionamento sarà proporzionale a N^2/4, cioè due volte più veloce dell'algoritmo precedente. Nella mia implementazione, a causa dell'uso non ottimale della permutazione, il tempo di esecuzione era più lungo di quello di Selection. Ho intenzione di correggere e aggiornare presto il post. Ecco il codice e il risultato della sua operazione sulla stessa macchina:

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

Ordinamento della shell. Ordinamento della shell

Un ragazzo intelligente, Donald Schell, notò nel 1959 che i casi più costosi nell'algoritmo per gli inserimenti sono quando l'elemento ritorna molto all'inizio dell'array: ad alcuni passaggi riportiamo l'elemento all'inizio di un paio di posizioni , e in un altro passaggio quasi attraverso l'intera schiera fino all'inizio è lungo e lungo. È possibile farlo contemporaneamente, saltando più elementi? E ha trovato un modo del genere. Consiste nell'eseguire in sequenza ordinamenti parziali speciali, generalmente chiamati d-sort o, secondo Sedgwick, h-sort (sospetto che h significhi hop). 3-sort, ad esempio, confronterà l'elemento in questione non con quello precedente, ma ne salterà due e lo confronterà con quello 3 posizioni indietro. Se modificato, lo confronterà nuovamente con l'elemento 3 posizioni indietro e così via. La conclusione è che l'array risultante sarà “3-sorted”, ovvero la posizione errata degli elementi sarà inferiore a 3 posizioni. Lavorare con questo algoritmo di inserimento sarà facile e piacevole. A proposito, "1-sort" non è altro che un semplice algoritmo di inserimento =) Applicando h-sort in sequenza all'array con valori h decrescenti, possiamo ordinare un array di grandi dimensioni più velocemente. Ecco come appare: Visualizza La sfida qui è come scegliere la giusta sequenza di ordinamenti parziali. In definitiva, la prestazione dell’algoritmo dipende da questo. La più comune è la sequenza proposta da Donald Knuth: h = h*3 + 1, cioè 1, 4, 13, 40, ... e così via fino a 1/3 della dimensione dell'array. Questa sequenza fornisce prestazioni decenti ed è anche facile da implementare. L'analisi dell'algoritmo richiede tonnellate di linguaggio ed è oltre le mie capacità. L'ampiezza dell'analisi è determinata anche dalle numerose varianti delle sequenze h. Empiricamente possiamo dire che la velocità dell'algoritmo è molto buona: verifica tu stesso: un milione di elementi in meno di un secondo! Ed ecco il codice Java con la sequenza Knut.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

Ordinamento delle bolle. Metodo delle bolle

Questo è un classico! Quasi tutti i programmatori alle prime armi implementano questo algoritmo. È talmente classico che il dottor Sedgwick non aveva nemmeno un'animazione, quindi ho dovuto fare il lavoro da solo. Visualizza Qui, ad ogni passaggio, attraversiamo l'array dall'inizio alla fine, scambiando gli elementi vicini che sono fuori ordine. Di conseguenza, gli elementi più grandi “fluttuano” (da qui il nome) fino alla fine dell’array. Iniziamo ogni nuovo passaggio sperando ottimisticamente che l'array sia già ordinato ( sorted = true). Alla fine del passaggio, se vediamo che abbiamo commesso un errore, iniziamo un nuovo passaggio. La difficoltà qui è che, ancora una volta, stiamo attraversando (quasi) l'intero array ad ogni passaggio. Il confronto avviene ad ogni passaggio, lo scambio avviene quasi ad ogni passaggio, il che rende questo algoritmo uno dei più lenti (se consideriamo quelli implementati razionalmente, e non lo "shaking sort" e altri simili). È interessante notare che formalmente anche qui la complessità sarà pari a O(N^2), ma il coefficiente è molto più alto di quello degli inserimenti e delle selezioni. Codice algoritmo:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

Tempo di funzionamento: senti la differenza: più di mezz'ora su un milione di elementi! Conclusione: non usare mai questo algoritmo!!!

Riassunto della prima parte

Di conseguenza, suggerisco di guardare la tabella generale per questi algoritmi. Puoi anche confrontare i risultati con il metodo integrato java.util.Arrays.sort(). Sembra una sorta di magia: cosa potrebbe essere più veloce di Shell? Scriverò di questo nella parte successiva. Lì esamineremo gli algoritmi di ordinamento rapido ampiamente utilizzati, nonché l'ordinamento di fusione, impareremo la differenza nei metodi per ordinare gli array da primitive e tipi di riferimento e anche conoscere un'interfaccia molto importante in questa materia Comparable;) Di seguito puoi studiare un grafico costruito su scala logaritmica utilizzando tabelle di dati. Più piatta è la linea, migliore è l'algoritmo =) Per chi vuole scaricare l'intero progetto ed eseguire test in autonomia, tenga il link: Java Ci vediamo nella prossima parte! =)