Shellsort

Ordinamento della shell, algoritmo: barre dei colori

Shellsort è un metodo di ordinamento sviluppato da Donald L. Shell nel 1959 , che si basa sul metodo di ordinamento dell'inserimento diretto ( ordinamento per inserimento ).

principio

In linea di principio, Shellsort utilizza il punto di inserimento. Cerca di compensare lo svantaggio che qui gli elementi della sequenza devono spesso essere spostati su lunghe distanze. Ciò rende inefficiente l'ordinamento degli inserimenti. Shellsort segue l'approccio secondo cui la sequenza viene prima suddivisa in singole sotto-sequenze e queste vengono ordinate. La divisione viene eseguita in un numero diverso in ogni fase. Gli elementi non vengono copiati per la divisione, ma gli elementi hanno una certa distanza costante l'uno dall'altro. Ad esempio, il fattore 4 significa divisione in 4 sotto-sequenze, i cui elementi sono formati dalla sequenza originale con spaziatura 4, cioè gli indici 0, 4, 8 ... formano una sotto-sequenza, gli indici 1, 5, 9 ... un'altra. Una volta completata la fase di ordinamento, la sequenza viene quindi chiamata 4 ordinati. L'intero ordinamento della shell quindi porta, ad esempio, a una sequenza che viene prima ordinata in 4, quindi in 2 e infine in 1, per così dire, con il normale ordinamento per inserzione.

Ciò potrebbe essere illustrato chiaramente utilizzando matrici ausiliarie (vedi esempio):

• I dati vengono scritti riga per riga in una matrice di k colonne
• Le colonne della matrice vengono ordinate individualmente

Ciò si traduce in uno smistamento approssimativo. Questo passaggio viene ripetuto più volte, la larghezza della matrice viene ridotta in ogni caso fino a quando la matrice non è composta da un'unica colonna completamente ordinata.

Importante: una sequenza ordinata a * b non viene automaticamente ordinata a o b! Per dimostrarlo, consideriamo una sequenza dei numeri da 1 a 12. Questa è 6 ordinata se seguiamo una qualsiasi permutazione dei numeri 1 ... 6 con qualsiasi permutazione dei numeri 7 ... 12. La permutazione 6, 5, 4, 3, 2, 1 non è affatto ordinata a 2 o 3.

 6, 5, 4, 3, 2, 1, 7, 8, 9, 10, 11, 12  ist 6-sortiert, aber nicht 2- und auch nicht 3-sortiert.

Shellsort funziona sul posto , ma non è uno degli algoritmi di ordinamento stabili . A causa dell'ordinamento sulla distanza, il metodo di ordinamento perde la sua proprietà "stabile". Due elementi adiacenti e ordinati finiscono in sottosequenze diverse e possono essere riorganizzati in modo che il loro ordine sia invertito.

esempio

I numeri 2, 5, 3, 4, 3, 9, 3, 2, 5, 4, 1, 3 devono essere ordinati utilizzando la sequenza ${\ displaystyle 2 ^ {n}, ..., 4,2,1}$

Per prima cosa i dati vengono inseriti riga per riga in una matrice con quattro colonne e ordinati colonna per colonna. La sequenza di numeri è quindi 4 ordinata.

2 5 3 4        2 4 1 2
3 9 3 2  →     3 5 3 3
5 4 1 3        5 9 3 4

La matrice a quattro colonne ordinata è ora divisa in due colonne, che si leggono da sinistra a destra. Queste colonne sono ora 2 ordinate.

2 4         1 2
1 2         2 3
3 5   →     3 4
3 3         3 4
5 9         3 5
3 4         5 9

La matrice ordinata a due colonne viene ora scritta su una riga e ordinata nuovamente utilizzando il normale ordinamento per inserzione. Il vantaggio qui è che nessun elemento della sequenza deve essere spostato fino alla posizione di inserimento, che viene applicata a una sequenza che non è stata preordinata.

1 2 2 3 3 4 3 4 3 5 5 9  →   1 2 2 3 3 3 3 4 4 5 5 9

La sequenza di passaggi qui utilizzata (come originariamente proposta da Shell nel 1959) non si rivela utile nella pratica, poiché solo le posizioni pari vengono ordinate e le posizioni dispari nella sequenza vengono toccate solo nell'ultimo passaggio. 1,4,13,40 ... si è dimostrato più utile (valore _n = 3 × valore _n-1 +1). ${\ displaystyle 1,2,4,8,16, ..., 2 ^ {n}}$

implementazione

Java 5

Shellsort è un miglioramento dell'algoritmo di inserimento diretto. Là gli elementi si muovono al loro posto in singoli passaggi: dopo aver trovato l'elemento più piccolo, gli elementi intermedi vengono spinti uno ad uno e solo i più piccoli "salti". La maggior parte (cioè, n) elementi vengono spinti dalla loro posizione originale alla loro posizione finale in una media di n / 3 passaggi.

Con l'ordinamento della shell si introducono dimensioni dei passi decrescenti k [1], k [2]… k [t], per cui la dimensione dell'ultimo passo è sempre k [t] = 1. I passaggi T vengono eseguiti uno dopo l'altro; nel passo m-esimo, gli elementi saltano nella direzione della loro posizione futura di k [m] posti. Nella prima fase, quegli elementi sono ordinati tra loro che sono k [1] posti distanti; poi quelli che sono a distanza k [2] l'uno dall'altro, ecc. L'effetto di questa procedura è che gli elementi "saltano" al loro posto nel primo passaggio, non uno, ma k [1] posti.

L'ultima dimensione del gradino k [t] è 1, ad es. H. Infine, viene eseguito un normale processo di smistamento per inserimento diretto. Ciò garantisce che la sequenza venga ordinata alla fine. Tuttavia, l'algoritmo non ha quasi bisogno di fare nulla perché i passaggi precedenti hanno quasi completamente ordinato l'ordine.

Lo sforzo di smistamento può essere notevolmente ridotto scegliendo opportunamente le dimensioni dei gradini k [1], k [2] ... k [t]. Per le dimensioni dei passi (1, 3, 7, 15, 31 ...) è stato dimostrato (vedi Donald E. Knuth : The Art of Computer Programming ) che la complessità temporale dell'algoritmo n è ^1.5 , che è significativamente migliore di quella complessità quadratica di bubble sort, insertion sort o selection sort , ma (almeno per grandi quantità di dati) peggiore della complessità n log n di mergesort o heapsort .

 static <E extends Comparable<? super E>> void shellSort(E[] sammlung, int[] schrittweiten) {
   for (int schrittweite : schrittweiten) { // straight insertion mit schrittweite
      for (int index = schrittweite; index < sammlung.length; index++){
         E elementZumEinfuegen = sammlung[index];
         int einfuegestelle = index;
         while (einfuegestelle - schrittweite >= 0 &&
               elementZumEinfuegen.compareTo(sammlung[einfuegestelle-schrittweite]) < 0) {
            sammlung[einfuegestelle] = sammlung[einfuegestelle - schrittweite];
            einfuegestelle -= schrittweite; // Sprung um schrittweite
         }
         sammlung[einfuegestelle] = elementZumEinfuegen;
      }
   }
 }

Giava

In effetti, i dati non sono organizzati sotto forma di una matrice, ma sotto forma di un campo unidimensionale. Le colonne sono formate da un'indicizzazione intelligente. Quindi tutti gli elementi a distanza h formano una colonna. Le colonne sono ordinate in base alla posizione di inserimento, poiché questo algoritmo può trarre vantaggio dal preordinamento dei dati.

Nel seguente programma, i dati vengono prima organizzati in colonne h = 2147483647, se sono disponibili tanti dati. In caso contrario, il ciclo for-i viene saltato e continuato con h = 1131376761 ecc.

void shellsort (int[] a, int n)
{
    int i, j, k, h, t;

    int[] spalten = {2147483647, 1131376761, 410151271, 157840433,
    58548857, 21521774, 8810089, 3501671, 1355339, 543749, 213331,
    84801, 27901, 11969, 4711, 1968, 815, 271, 111, 41, 13, 4, 1};

    for (k = 0; k < spalten.length; k++)
    {
        h = spalten[k];
        // Sortiere die "Spalten" mit Insertionsort
        for (i = h; i < n; i++)
        {
            t = a[i];
            j = i;
            while (j >= h && a[j-h] > t)
            {
                a[j] = a[j-h];
                j = j - h;
            }
            a[j] = t;
        }
    }
}

Complessità e conseguenze a distanza

La complessità di Shellsort dipende dalla scelta della sequenza di distanze per il numero di colonne h. Per varie conseguenze sono stati dimostrati limiti massimi di complessità, che forniscono quindi un'indicazione della durata. La maggior parte del lavoro teorico sulle conseguenze considera solo il numero di confronti come un importante fattore di costo. Tuttavia, le implementazioni reali mostrano che i loop e le azioni di copia svolgono anche un ruolo decisivo negli array non enormi.

In origine Donald Shell proponeva le serie 1, 2, 4, 8, 16, 32…, 2 ^k . Le prestazioni sono pessime, tuttavia, perché gli elementi vengono ordinati in posizioni dispari solo nell'ultimo passaggio. La complessità è molto alta. ${\ displaystyle \ Theta (n ^ {2})}$

Con la sequenza 1, 3, 7, 15, 31, 63…, 2 ^k - 1 di Hibbard si ottiene una complessità di . ${\ displaystyle {\ mathcal {O}} (n ^ {1,5})}$

Con la sequenza 1, 2, 3, 4, 6, 8, 9, 12, 16…, 2 ^p 3 ^q di Pratt, la complessità è . ${\ displaystyle {\ mathcal {O}} (n \ cdot \ log (n) ^ {2})}$

Donald E. Knuth ha anche fatto alcuni episodi per Shellsort. Uno di quelli comunemente usati in letteratura è il seguente: 1, 4, 13, 40, 121, 364, 1093…, (3 ^k -1) / 2. La regola di calcolo per la stessa sequenza è meglio conosciuta: 3h _k-1 + 1. La complessità è . ${\ displaystyle {\ mathcal {O}} (n ^ {1,5})}$

Alcuni buoni episodi sono di Robert Sedgewick . La sequenza 1, 8, 23, 77, 281, 1073, 4193, 16577…, 4 ^{k + 1} + 3 * 2 ^k + 1 ha raggiunto la complessità di . Una sequenza molto migliore è la seguente: 1, 5, 19, 41, 109, 209, 505, 929, 2161, 3905, 8929, 16001 ..., 9 * 2 ^k - 9 * 2 ^{k / 2} + 1 (k pari) o . 8 * 2 ^k - 6 * 2 ^{(k + 1) / 2} + 1 (k dispari) ${\ displaystyle {\ mathcal {O}} (n ^ {4/3})}$

Se si considerano sequenze puramente geometriche, c'è un minimo nell'area più ampia del fattore 2.3, ad es. H. i seguenti membri hanno il rapporto di circa 2,3. Una delle sequenze teoricamente migliori (cioè il numero di confronti) determinata sperimentalmente da Marcin Ciura è 1, 4, 10, 23, 57, 132, 301, 701, 1750 e si basa su questo fattore. In base al fattore 1750/701, la serie continua come segue: Sia g l'ultimo termine, quindi il successivo è dato da 1 + floor (2,5 * g), ovvero 701, 1753, 4383, 10958, 27396, 68491 , 171228… Una serie di Gonnet e Baeza-Yates si basa su un fattore di 2,2, che dà ottimi risultati.

Sorprendentemente, in pratica si conoscono sequenze migliori di quelle di Marcin Ciura, che vengono calcolate ricorsivamente. Il tempo di esecuzione dell'ordinamento della shell è più breve, sebbene il numero di confronti sia maggiore (gli elementi da ordinare sono numeri interi nella larghezza del registro). Le sequenze ricorsive sono calcolate da numeri interi e il rapporto dei seguenti membri converge a un certo valore; per i numeri di Fibonacci è il rapporto aureo .

Una tale sequenza è basata sui numeri di Fibonacci . Uno dei due 1 all'inizio viene omesso e ogni numero nella sequenza viene elevato alla potenza del doppio della sezione aurea (circa 3.236), che quindi porta a questa sequenza di distanza: 1, 9, 34, 182, 836, 4025, 19001, 90358, 428481 , 2034035 ...

Un'altra sequenza ricorsiva è stata trovata da Matthias Fuchs. La sequenza 1, 4, 13, 40, 124, 385, 1195, 3709, 11512, 35731 ... ha un valore di convergenza di circa 3.103803402. La regola di calcolo è f _{k + 1} = 3 * f _k + f _k-2 , per cui la sequenza inizia inizialmente con 1, 1, 1 e i primi due 1 vengono omessi per l'ordinamento shell.

Altre sequenze non sono costanti, ma vengono calcolate dal numero corrente di elementi nell'array. Vengono inizializzati con questo numero e diminuiscono fino a raggiungere 1.
Robert Kruse: h _k-1 = h _k / 3 + 1
Gonnet e Baeza-Yates: h _k-1 = (5 * h _k - 1) / 11

Entrambi gli episodi hanno una performance leggermente peggiore rispetto ai due episodi ricorsivi e gli episodi molto buoni di Sedgewick e quello di Marcin Ciura. Ma possono essere integrati direttamente nell'algoritmo di ordinamento della shell.

L'esistenza di una sequenza con la complessità è già stata esclusa in un'opera di Bjorn Poonen , Plaxton e Suel. Ma si potrebbe dimostrare che in linea di principio per n sufficientemente grande si può sempre trovare una sequenza con una complessità di . ${\ displaystyle {\ mathcal {O}} (n \ cdot \ log (n))}$${\ displaystyle {\ mathcal {O}} (n ^ {1+ \ varepsilon})}$

La ricerca di una sequenza ottimale risulta essere estremamente difficile. Gli spazi tra i seguenti elementi che sono troppo grandi comportano turni troppo grandi, mentre gli spazi troppo stretti causano troppi passaggi fino allo smistamento finale. Quando si sceglie una sequenza, è importante evitare che due termini successivi della sequenza abbiano fattori comuni, poiché una sequenza ordinata a * b e un successivo ordinamento a * c escludono alcune sotto-sequenze dall'ordinamento (vedere la nota sulla sequenza originale 1, 2, 4, 8, 16 ..., che omette i dispari e li tiene in considerazione solo durante l'ordinamento 1). Questo è sicuramente un vantaggio su diversi link.

Uno dei principali vantaggi dell'algoritmo di ordinamento della shell rispetto ad altri è che può trarre vantaggio dall'ordinamento già esistente. Non importa se l'array è ordinato o inversamente ordinato. Entrambi i casi sono volte più veloci di un array ordinato in modo puramente casuale. Con solo 65536 elementi il ​​vantaggio in termini di velocità è di circa il fattore 4, con 128 è ancora maggiore del fattore 2.

Variazioni

Combsort funziona in modo simile a Shellsort. L' ordinamento delle colonne viene ordinato solo con un passaggio di Bubble Sort prima che il numero di colonne venga ridotto.

letteratura

• Donald L. Shell : una procedura di smistamento ad alta velocità. In: Timon N. Commun. ACM , 2 (7), 1959, pagg. 30-32.
• Robert Sedgewick : Algoritmi in Java , Parte 1–4. Addison-Wesley, ISBN 0-201-36120-5

link internet

• Complessità di Shellsort