Shellsort - Shellsort

Shellsort

Shellsort con spazi 23, 10, 4, 1 in azione
Classe	Algoritmo di ordinamento
Struttura dati	Vettore
Prestazioni nel caso peggiore	O( n 2 ) (sequenza di gap peggiore nota nel caso peggiore) O( n log 2 n ) (sequenza di gap peggiore nota nel caso peggiore)
Best-caso le prestazioni	O( n log n ) (la maggior parte delle sequenze gap) O( n log 2 n ) (sequenza gap più nota nel caso peggiore)
Prestazioni medie	dipende dalla sequenza di spazi
Complessità dello spazio nel caso peggiore	О( n ) totale, O(1) ausiliario

Scambiare coppie di elementi in passaggi successivi di Shellsort con spazi 5, 3, 1

Shellsort , noto anche come Shell sort o Shell's method , è un ordinamento di confronto sul posto . Può essere visto come una generalizzazione dell'ordinamento per scambio ( bubble sort ) o dell'ordinamento per inserimento ( inserimento ordinamento ). Il metodo inizia ordinando coppie di elementi distanti tra loro, quindi riducendo progressivamente il divario tra gli elementi da confrontare. Partendo da elementi distanti, può spostare alcuni elementi fuori posto in posizione più velocemente di un semplice scambio di vicini più vicini. Donald Shell ha pubblicato la prima versione di questo tipo nel 1959. Il tempo di esecuzione di Shellsort dipende fortemente dalla sequenza di spazi che utilizza. Per molte varianti pratiche, la determinazione della loro complessità temporale rimane un problema aperto .

Descrizione

Shellsort è un'ottimizzazione dell'ordinamento per inserzione che consente lo scambio di elementi distanti tra loro. L'idea è di organizzare l'elenco degli elementi in modo che, partendo da qualsiasi punto, prendendo ogni h- esimo elemento si produca un elenco ordinato. Si dice che tale elenco è h -sorted. Può anche essere pensato come h elenchi interlacciati, ciascuno ordinato individualmente. Iniziare con grandi valori di h consente agli elementi di spostarsi a lunghe distanze nell'elenco originale, riducendo rapidamente grandi quantità di disordine e lasciando meno lavoro da eseguire per passaggi h -sort più piccoli . Se l'elenco è poi k-ordinato per qualche intero più piccolo k , allora l'elenco rimane h- ordinato. Seguendo questa idea per una sequenza decrescente di valori h che terminano con 1 è garantito che alla fine lascerà un elenco ordinato.

In termini semplicistici, questo significa che se abbiamo un array di 1024 numeri, il nostro primo intervallo ( h ) potrebbe essere 512. Quindi esaminiamo l'elenco confrontando ogni elemento nella prima metà con l'elemento nella seconda metà. Il nostro secondo gap ( k ) è 256, che suddivide l'array in quattro sezioni (a partire da 0,256,512,768) e ci assicuriamo che i primi elementi in ogni sezione siano ordinati l'uno rispetto all'altro, quindi il secondo elemento in ogni sezione e così via . In pratica la sequenza dei gap potrebbe essere qualsiasi cosa, ma l'ultimo gap è sempre 1 per terminare l'ordinamento (in effetti terminando con un normale ordinamento per inserimento).

Di seguito è mostrato un esempio di esecuzione di Shellsort con i gap 5, 3 e 1.

Il primo passaggio, 5-ordinamento, esegue l'ordinamento per inserimento su cinque sottoarray separati ( a ₁ , a ₆ , a ₁₁ ), ( a ₂ , a ₇ , a ₁₂ ), ( a ₃ , a ₈ ), ( a ₄ , a ₉ ), ( a ₅ , a ₁₀ ). Ad esempio, cambia il sottoarray ( a ₁ , a ₆ , a ₁₁ ) da (62, 17, 25) a (17, 25, 62). Il passaggio successivo, 3-ordinamento, esegue l'ordinamento per inserzione sui tre sottoarray ( a ₁ , a ₄ , a ₇ , a ₁₀ ), ( a ₂ , a ₅ , a ₈ , a ₁₁ ), ( a ₃ , a ₆ , un ₉ , un ₁₂ ). L'ultimo passaggio, 1-sorting, è un normale ordinamento di inserimento dell'intero array ( a ₁ ,..., a ₁₂ ).

Come illustra l'esempio, i sottoarray su cui opera Shellsort sono inizialmente brevi; poi sono più lunghe ma quasi ordinate. In entrambi i casi l'ordinamento per inserimento funziona in modo efficiente.

Shellsort non è stabile : può cambiare l'ordine relativo degli elementi con valori uguali. È un algoritmo di ordinamento adattivo in quanto viene eseguito più velocemente quando l'input è parzialmente ordinato.

Pseudocodice

Usando la sequenza di spazi vuoti di Marcin Ciura, con un ordinamento di inserimento interno.

# Sort an array a[0...n-1].
gaps = [701, 301, 132, 57, 23, 10, 4, 1]  // Ciura gap sequence

# Start with the largest gap and work down to a gap of 1
foreach (gap in gaps)
{
    # Do a gapped insertion sort for this gap size.
    # The first gap elements a[0..gap-1] are already in gapped order
    # keep adding one more element until the entire array is gap sorted
    for (i = gap; i < n; i += 1)
    {
        # add a[i] to the elements that have been gap sorted
        # save a[i] in temp and make a hole at position i
        temp = a[i]
        # shift earlier gap-sorted elements up until the correct location for a[i] is found
        for (j = i; j >= gap and a[j - gap] > temp; j -= gap)
        {
            a[j] = a[j - gap]
        }
        # put temp (the original a[i]) in its correct location
        a[j] = temp
    }
}

sequenze gap

La questione di decidere quale sequenza di spazi utilizzare è difficile. Ogni sequenza di spazi che contiene 1 produce un ordinamento corretto (dato che questo rende il passaggio finale un normale ordinamento per inserzione); tuttavia, le proprietà delle versioni di Shellsort così ottenute possono essere molto diverse. Troppi spazi vuoti rallentano i passaggi e troppi spazi generano un sovraccarico.

La tabella seguente mette a confronto la maggior parte delle sequenze di gap proposte pubblicate finora. Alcuni di essi hanno elementi decrescenti che dipendono dalla dimensione dell'array ordinato ( N ). Altri stanno aumentando le sequenze infinite, i cui elementi minori di N dovrebbero essere usati in ordine inverso.

OEIS	Termine generale ( k ≥ 1)	Lacune concrete	Complessità temporale nel caso peggiore	Autore e anno di pubblicazione
	${\displaystyle \left\lfloor {\frac {N}{2^{k}}}\right\rfloor }$	${\displaystyle \left\lfloor {\frac {N}{2}}\right\rfloor,\left\lfloor {\frac {N}{4}}\right\rfloor,\ldots,1}$	${\displaystyle \Theta \left(N^{2}\right)}$[es. quando N = 2 p ]	Conchiglia , 1959
	${\displaystyle 2\left\lfloor {\frac {N}{2^{k+1}}}\right\rfloor +1}$	${\displaystyle 2\left\lfloor {\frac {N}{4}}\right\rfloor +1,\ldots,3,1}$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Frank & Lazzaro, 1960
A000225	${\displaystyle 2^{k}-1}$	${\displaystyle 1,3,7,15,31,63,\ldots}$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Hibbard , 1963
A083318	${\displaystyle 2^{k}+1}$, preceduto da 1	${\displaystyle 1,3,5,9,17,33,65,\ldots}$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Papernov & Stasevich, 1965
A003586	Numeri successivi della forma ( 3 numeri lisci ) ${\displaystyle 2^{p}3^{q}}$	${\displaystyle 1,2,3,4,6,8,9,12,\ldots}$	${\displaystyle \Theta \left(N\log ^{2}N\right)}$	Pratt , 1971
A003462	${\displaystyle {\frac {3^{k}-1}{2}}}$, non maggiore di ${\displaystyle \left\lceil {\frac {N}{3}}\right\rceil}$	${\displaystyle 1,4,13,40,121,\ldots}$	${\displaystyle \Theta \left(N^{\frac {3}{2}}\right)}$	Knuth , 1973, basato su Pratt , 1971
A036569	${\displaystyle {\begin{allineato}&\prod \limits _{I}a_{q},{\hbox{dove}}\\a_{0}={}&3\\a_{q}={}& \min \left\{n\in \mathbb {N} \colon n\geq \left({\frac {5}{2}}\right)^{q+1},\forall p\colon 0\leq p<q\Rightarrow \gcd(a_{p},n)=1\right\}\\I={}&\left\{0\leq q<r\mid q\neq {\frac {1}{ 2}}\left(r^{2}+r\right)-k\right\}\\r={}&\left\lfloor {\sqrt {2k+{\sqrt {2k}}}}\right\ rfloor \end{allineato}}}$	${\displaystyle 1,3,7,21,48,112,\ldots}$	${\displaystyle O\left(N^{1+{\sqrt {\frac {8\ln\left(5/2\right)}{\ln(N)}}}}\right)}$	Incerpi & Sedgewick , 1985, Knuth
A036562	${\displaystyle 4^{k}+3\cdot 2^{k-1}+1}$, preceduto da 1	${\displaystyle 1,8,23,77,281,\ldots}$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	Sedgewick, 1982
A033622	${\displaystyle {\begin{cases}9\left(2^{k}-2^{\frac {k}{2}}\right)+1&k{\text{even}},\\8\cdot 2 ^{k}-6\cdot 2^{(k+1)/2}+1&k{\text{ dispari}}\end{casi}}}$	${\displaystyle 1,5,19,41,109,\ldots}$	${\displaystyle O\left(N^{\frac {4}{3}}\right)}$	Sedgewick, 1986
	${\displaystyle h_{k}=\max \left\{\left\lfloor {\frac {5h_{k-1}-1}{11}}\right\rfloor ,1\right\},h_{0} =N}$	${\displaystyle \left\lfloor {\frac {5N-1}{11}}\right\rfloor,\left\lfloor {\frac {5}{11}}\left\lfloor {\frac {5N-1} {11}}\right\rfloor -1\right\rfloor ,\ldots ,1}$	Sconosciuto	Gonnet & Baeza-Yates , 1991
A108870	${\displaystyle \left\lceil {\frac {1}{5}}\left(9\cdot \left({\frac {9}{4}}\right)^{k-1}-4\right) \right\rceil }$	${\displaystyle 1,4,9,20,46,103,\ldots}$	Sconosciuto	Tokuda, 1992
A102549	Sconosciuto (derivato sperimentalmente)	${\displaystyle 1,4,10,23,57,132,301.701}$	Sconosciuto	Ciura, 2001

Quando la rappresentazione binaria di N contiene molti zeri consecutivi, Shellsort utilizzando la sequenza gap originale di Shell effettua confronti Θ( N ² ) nel caso peggiore. Ad esempio, questo caso si verifica per N pari a una potenza di due quando elementi maggiori e minori della mediana occupano rispettivamente posizione pari e dispari, poiché vengono confrontati solo nell'ultimo passaggio.

Sebbene abbia una complessità maggiore rispetto a O ( N  log  N ) che è ottimale per gli ordinamenti di confronto, la versione di Pratt si presta a reti di ordinamento e ha la stessa complessità di porta asintotica del sorter bitonico di Batcher .

Gonnet e Baeza-Yates hanno osservato che Shellsort effettua in media il minor numero di confronti quando i rapporti dei gap successivi sono approssimativamente uguali a 2,2. Questo è il motivo per cui la loro sequenza con rapporto 2,2 e la sequenza di Tokuda con rapporto 2,25 si dimostrano efficienti. Tuttavia, non si sa perché sia ​​così. Sedgewick consiglia di utilizzare spazi che hanno divisori comuni massimi bassi o sono coprimi a due a due .

Rispetto al numero medio di confronti, la sequenza di Ciura ha le prestazioni più note; le lacune da 701 non sono state determinate ma la sequenza può essere ulteriormente estesa secondo la formula ricorsiva . ${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$

La sequenza di Tokuda, definita dalla semplice formula , dove , , può essere consigliata per applicazioni pratiche. ${\displaystyle h_{k}=\lceil h'_{k}\rceil }$${\displaystyle h'_{k}=2.25h'_{k-1}+1}$${\displaystyle h'_{1}=1}$

Se la dimensione massima dell'input è piccola, come può accadere se Shellsort viene utilizzato su piccoli sottoarray da un altro algoritmo di ordinamento ricorsivo come quicksort o merge sort , allora è possibile tabulare una sequenza ottimale per ogni dimensione di input.

Complessità computazionale

Vale la seguente proprietà: dopo h ₂ -sorting di qualsiasi array h ₁ -sorted, l'array rimane h ₁ -sorted. Ogni array h ₁ ordinato e h ₂ ordinato è anche ( a ₁ h ₁ + a ₂ h ₂ ) ordinato, per tutti gli interi non negativi a ₁ e a ₂ . La complessità del caso peggiore di Shellsort è quindi connessa con il problema di Frobenius : dati interi h ₁ ,..., h _n con mcd = 1, il numero di Frobenius g ( h ₁ ,..., h _n ) è il massimo intero che non può essere rappresentato come a ₁ h ₁ + ... + a _n h _n con intero non negativo a ₁ ,..., a _n . Utilizzando formule note per i numeri di Frobenius, possiamo determinare la complessità del caso peggiore di Shellsort per diverse classi di sequenze gap. I risultati provati sono mostrati nella tabella sopra.

Rispetto al numero medio di operazioni, nessuno dei risultati provati riguarda una pratica gap sequence. Per gap che sono potenze di due, Espelid ha calcolato questa media come . Knuth ha determinato la complessità media dell'ordinamento di un array di N elementi con due spazi ( h , 1) come . Ne consegue che uno Shellsort a due passaggi con h = ( N ^1/3 ) effettua in media O ( N ^5/3 ) confronti/inversioni/tempo di esecuzione. Yao ha trovato la complessità media di uno Shellsort a tre passaggi. Il suo risultato è stato affinato da Janson e Knuth: il numero medio di confronti/inversioni/tempo di esecuzione effettuati durante uno Shellsort con tre gap ( ch , cg , 1), dove h e g sono coprimi, è nel primo passaggio, nel secondo passaggio e nel terzo passaggio. ψ ( h , g ) nell'ultima formula è una funzione complicata asintoticamente uguale a . In particolare, quando h = Θ( N ^7/15 ) eg = Θ( N ^1/5 ), il tempo medio di smistamento è O ( N ^23/15 ). ${\displaystyle 0,5349N{\sqrt {N}}-0,4387N-0,097{\sqrt {N}}+O(1)}$${\displaystyle {\frac {2N^{2}}{h}}+{\sqrt {\pi N^{3}h}}}$${\displaystyle {\frac {N^{2}}{4ch}}+O(N)}$${\displaystyle {\frac {1}{8g}}{\sqrt {\frac {\pi}{ch}}}(h-1)N^{3/2}+O(hN)}$${\displaystyle \psi (h,g)N+{\frac {1}{8}}{\sqrt {\frac {\pi }{c}}}(c-1)N^{3/2}+O \left((c-1)gh^{1/2}N\right)+O\left(c^{2}g^{3}h^{2}\right)}$${\displaystyle {\sqrt {\frac {\pi h}{128}}}g+O\left(g^{-1/2}h^{1/2}\right)+O\left(gh^ {-1/2}\destra)}$

Sulla base di esperimenti, si ipotizza che Shellsort con la sequenza gap di Hibbard funzioni in un tempo medio O ( N ^5/4 ) e che la sequenza di Gonnet e Baeza-Yates richieda in media 0,41 N  ln  N  (ln ln  N  + 1/6 ) elemento si sposta. Le approssimazioni del numero medio di operazioni precedentemente proposte per altre sequenze falliscono quando gli array ordinati contengono milioni di elementi.

Il grafico sottostante mostra il numero medio di confronti di elementi in varie varianti di Shellsort, diviso per il limite inferiore teorico, ovvero log ₂ N !, dove la sequenza 1, 4, 10, 23, 57, 132, 301, 701 è stata estesa secondo la formula . ${\displaystyle h_{k}=\lfloor 2.25h_{k-1}\rfloor }$

Applicando la teoria della complessità di Kolmogorov , Jiang, Li e Vitányi hanno dimostrato il seguente limite inferiore per l'ordine del numero medio di operazioni/tempo di esecuzione in uno Shellsort p- pass: Ω( pN ^{1+1/ p} ) quando p  log ₂ N e Ω( pN ) quando p  > log ₂ N . Pertanto, Shellsort ha prospettive di esecuzione in un tempo medio che cresce asintoticamente come N log N solo quando si utilizzano sequenze di gap il cui numero di gap cresce in proporzione al logaritmo della dimensione dell'array. Tuttavia, non è noto se Shellsort possa raggiungere questo ordine asintotico di complessità del caso medio, che è ottimale per gli ordinamenti di confronto. Il limite inferiore è stato migliorato da Vitányi per ogni numero di passaggi fino a dove . Questo risultato implica, ad esempio, il limite inferiore di Jiang-Li-Vitányi per tutte le sequenze di incremento -pass e migliora tale limite inferiore per particolari sequenze di incremento. Infatti tutti i limiti (inferiore e superiore) attualmente noti per il caso medio sono esattamente abbinati a questo limite inferiore. Ad esempio, questo dà il nuovo risultato che il limite superiore Janson-Knuth è abbinato al limite inferiore risultante per la sequenza di incremento utilizzata, mostrando che Shellsort a tre passaggi per questa sequenza di incremento utilizza confronti/inversioni/tempo di esecuzione. La formula ci permette di cercare sequenze di incremento che producono limiti inferiori sconosciuti; ad esempio una sequenza di incremento per quattro passaggi che ha un limite inferiore maggiore rispetto alla sequenza di incremento . Il limite inferiore diventa ${\displaystyle p}$${\displaystyle \Omega (N\sum _{k=1}^{p}h_{k-1}/h_{k})}$${\displaystyle h_{0}=N}$${\displaystyle p}$${\displaystyle \Theta (N^{23/15})}$${\displaystyle \Omega (pn^{1+1/p})=\Omega (n^{5/4})}$${\displaystyle h_{1}=n^{11/16},}$ ${\displaystyle h_{2}=n^{7/16},}$ ${\displaystyle h_{3}=n^{3/16},}$ ${\displaystyle h_{4}=1}$${\displaystyle T=\Omega (n\cdot (n^{1-11/16}+n^{11/16-7/16}+n^{7/16-3/16}+n^{3 /16})=\Omega (n^{1+5/16})=\Omega (n^{21/16}).}$

La complessità nel peggiore dei casi di qualsiasi versione di Shellsort è di ordine superiore: Plaxton, Poonen e Suel hanno dimostrato che cresce almeno alla stessa velocità di . ${\displaystyle \Omega \left(N\left({\log N\over \log \log N}\right)^{2}\right)}$

Applicazioni

Shellsort esegue più operazioni e ha un tasso di errore della cache più elevato rispetto a Quicksort . Tuttavia, poiché può essere implementato utilizzando poco codice e non utilizza lo stack di chiamate , alcune implementazioni della funzione qsort nella libreria standard C destinata ai sistemi embedded la utilizzano invece di Quicksort. Shellsort è, ad esempio, utilizzato nella libreria uClibc . Per ragioni simili, in passato, nel kernel Linux veniva utilizzato Shellsort .

Shellsort può anche fungere da sotto-algoritmo di ordinamento introspettivo , per ordinare brevi sottoarray e per prevenire un rallentamento quando la profondità di ricorsione supera un determinato limite. Questo principio è impiegato, ad esempio, nel compressore bzip2 .

Guarda anche

• Ordinamento a pettine

Riferimenti

Bibliografia

• Knuth, Donald E. (1997). "Metodo Shell". L'arte della programmazione informatica. Volume 3: Ordinamento e ricerca (2a ed.). Reading, Massachusetts: Addison-Wesley. pp. 83-95. ISBN 978-0-201-89685-5.
• Analisi di Shellsort e algoritmi correlati , Robert Sedgewick, Quarto Simposio europeo sugli algoritmi, Barcellona, ​​settembre 1996.

link esterno

• Algoritmi di ordinamento animati: Shell Sort alla Wayback Machine (archiviato il 10 marzo 2015) - dimostrazione grafica
• Shellsort con spazi 5, 3, 1 come una danza popolare ungherese