Ordinamento shell in Java

1. Introduzione

In questo tutorial, descriveremo l'algoritmo di ordinamento della shell in Java.

2. Panoramica sull'ordinamento della shell

2.1. Descrizione

Descriviamo prima l'algoritmo di ordinamento della shell in modo da sapere cosa stiamo cercando di implementare.

L'ordinamento della shell si basa sull'algoritmo di ordinamento per inserimento e appartiene al gruppo degli algoritmi molto efficienti. In generale, l'algoritmo suddivide un set originale in sottoinsiemi più piccoli e quindi ciascuno di essi viene ordinato utilizzando l'ordinamento per inserimento .

Ma il modo in cui crea i sottoinsiemi non è semplice. Non sceglie gli elementi vicini per formare un sottoinsieme come ci si potrebbe aspettare. Piuttosto, l'ordinamento della shell utilizza il cosiddetto intervallo o intervallo per la creazione di sottoinsiemi. Ad esempio, se abbiamo lo spazio I , significa che un sottoinsieme conterrà gli elementi che si trovano in posizioni I distanti.

In primo luogo, l'algoritmo ordina gli elementi che sono lontani l'uno dall'altro. Quindi, il divario diventa più piccolo e vengono confrontati elementi più vicini. In questo modo, alcuni elementi che non sono in una posizione corretta possono essere posizionati più velocemente che se avessimo creato i sottoinsiemi dagli elementi vicini.

2.2. Un esempio

Vediamo questo nell'esempio con gli spazi di 3 e 1 e l'elenco non ordinato di 9 elementi:

Se seguiamo la descrizione precedente, nella prima iterazione avremo tre sottoinsiemi con 3 elementi (evidenziati dallo stesso colore):

Dopo aver ordinato ciascuno dei sottoinsiemi nella prima iterazione, l'elenco sarà simile a:

Possiamo notare che, sebbene non abbiamo ancora un elenco ordinato, gli elementi sono ora più vicini alle posizioni desiderate.

Infine, dobbiamo fare un altro ordinamento con l'incremento di uno ed è in realtà un ordinamento per inserzione di base. Il numero di operazioni di spostamento che dobbiamo eseguire per ordinare un elenco è ora inferiore a quello che sarebbe il caso se non facessimo la prima iterazione:

2.3. Scelta delle sequenze di gap

Come accennato, l'ordinamento della shell ha un modo unico di scegliere le sequenze di intervalli. Questo è un compito difficile e dovremmo stare attenti a non scegliere troppo pochi o troppi gap. Maggiori dettagli possono essere trovati nell'elenco delle sequenze di gap più proposte.

3. Implementazione

Diamo ora un'occhiata all'implementazione. Useremo la sequenza originale di Shell per gli incrementi di intervallo:

N/2, N/4, …, 1 (continuously dividing by 2)

L'implementazione in sé non è troppo complessa:

public void sort(int arrayToSort[]) { int n = arrayToSort.length; for (int gap = n / 2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arrayToSort[j - gap] > key) { arrayToSort[j] = arrayToSort[j - gap]; j -= gap; } arrayToSort[j] = key; } } }

Per prima cosa abbiamo creato una sequenza di gap con un ciclo for e poi abbiamo eseguito l'ordinamento per inserimenti per ciascuna dimensione di gap.

Ora possiamo facilmente testare il nostro metodo:

@Test public void givenUnsortedArray_whenShellSort_thenSortedAsc() { int[] input = {41, 15, 82, 5, 65, 19, 32, 43, 8}; ShellSort.sort(input); int[] expected = {5, 8, 15, 19, 32, 41, 43, 65, 82}; assertArrayEquals("the two arrays are not equal", expected, input); }

4. Complessità

In generale, l'algoritmo di ordinamento della shell è molto efficiente con elenchi di medie dimensioni . La complessità è difficile da determinare poiché dipende molto dalla sequenza dei gap, ma la complessità temporale varia tra O (N) e O (N ^ 2) .

La complessità dello spazio nel caso peggiore è O (N) con O (1) spazio ausiliario.

5. conclusione

In questo tutorial, abbiamo descritto l'ordinamento della shell e illustrato come implementarlo in Java.

Come al solito, l'intero codice può essere trovato su GitHub.