Algoritmo di ordinamento Shell con esempio

Cos'è l'algoritmo Shell Sort?

L'algoritmo Shell Sort, noto anche come metodo di Shell, è un algoritmo di ordinamento efficiente basato sul confronto in loco. Prende il nome da Donald Shell, che introdusse l'idea nel 1959, ed è un'estensione generalizzata dell'ordinamento per inserimento che ne supera il comportamento quadratico su dati sparsi.

L'idea fondamentale è quella di raggruppare gli elementi distanti tra loro, ordinare ciascun gruppo utilizzando l'algoritmo di ordinamento per inserimento e ridurre gradualmente la distanza fino a raggiungere uno. A quel punto, l'array è quasi ordinato.

Questo spazio, l'intervallo, segue una sequenza scelta come l'originale di Shell, di Knuth, di Hibbard o di Sedgewick. L'originale di Shell è n/2, n/4, ..., 1.

Algoritmo di ordinamento della shell

Passo 1) Inizializza il valore dell'intervallo h = n/2, dove n è la dimensione dell'array.

Passo 2) Inserisci in una sottolista tutti gli elementi che si trovano entro una distanza dell'intervallo h.

Passo 3) Ordina ciascuna sottolista utilizzando l'ordinamento per inserimento.

Passo 4) Imposta un nuovo intervallo h = h/2.

Passo 5) Se h > 0, torna al passaggio 2. Altrimenti, vai al passaggio 6.

Passo 6) L'array risultante è ora completamente ordinato.

Come funziona l'ordinamento della shell

Nell'ordinamento per inserimento, gli elementi si spostano di una sola posizione alla volta. L'ordinamento Shell, invece, divide l'array in sottoliste ampiamente distanziate in base all'intervallo e applica l'ordinamento per inserimento a ciascuna sottolista.

Man mano che l'intervallo si riduce, la dimensione della sottolista aumenta. Poiché i passaggi precedenti lasciano i dati parzialmente ordinati, intervalli più piccoli richiedono molti meno scambi rispetto all'esecuzione ordinamento per inserzione Partendo da zero. La figura seguente illustra una singola passata di Shell Sort.

Funzionamento dell'algoritmo Shell Sort con esempio

Ordiniamo l'array seguente utilizzando l'algoritmo Shell Sort.

Passo 1) La dimensione dell'array è 8, quindi il valore iniziale dell'intervallo è h = 8/2 = 4.

Passo 2) Gli elementi del gruppo distano quattro posizioni l'uno dall'altro. Sottoliste: {8, 1}, {6, 4}, {7, 5}, {2, 3}.

Passo 3) Ordina ciascuna sottolista utilizzando l'ordinamento per inserimento. Una variabile temporanea memorizza il valore inserito durante lo spostamento degli elementi. Dopo gli scambi, l'array si presenta in questo modo.

Passo 4) Diminuisci l'intervallo. Il nuovo intervallo è h = 4/2 = 2.

Passo 5) Poiché 2 > 0, torna al passaggio 2 e raggruppa gli elementi distanti due posizioni: {1, 5, 8, 7} e {4, 2, 6, 3}.

Ordina la prima sottolista. L'array diventa:

Dopo aver ordinato la seconda sottolista:

Diminuisci nuovamente l'intervallo a h = 2/2 = 1. Con un intervallo di uno, Shell Sort esegue un passaggio finale di ordinamento per inserimento sull'intero array, come mostrato di seguito.

Passo 6) Dividendo nuovamente l'intervallo si ottiene 0. L'array è ora completamente ordinato:

Pseudo-Code per Shell Sort

Start
Input array a of size n
for (interval = n / 2; interval > 0; interval /= 2)
    for (i = interval; i < n; i += 1)
        temp = a[i];
        for (j = i; j >= interval && a[j - interval] > temp; j -= interval)
            a[j] = a[j - interval];
        a[j] = temp;
End

Programma di ordinamento della shell in C/C++

Ingresso:

//Shell Sort Program in C/C++
#include <bits/stdc++.h>
using namespace std;
void ShellSort(int data[], int size) {
    for (int interval = size / 2; interval > 0; interval /= 2) {
        for (int i = interval; i < size; i += 1) {
            int temp = data[i];
            int j;
            for (j = i; j >= interval && data[j - interval] > temp; j -= interval) {
                data[j] = data[j - interval];
            }
            data[j] = temp;
        }
    }
}
int main() {
    int data[] = {8, 6, 7, 2, 1, 4, 5, 3};
    int size = sizeof(data) / sizeof(data[0]);
    ShellSort(data, size);
    cout << "Sorted Output: \n";
    for (int i = 0; i < size; i++)
        cout << data[i] << " ";
    cout << "\n";
}

Produzione:

Sorted Output:

1 2 3 4 5 6 7 8

Esempio di ordinamento della shell in Python

Ingresso:

#Shell Sort Example in Python
def ShellSort(data, size):
    interval = size // 2
    while interval > 0:
        for i in range(interval, size):
            temp = data[i]
            j = i
            while j >= interval and data[j - interval] > temp:
                data[j] = data[j - interval]
                j -= interval
            data[j] = temp
        interval //= 2
data = [8, 6, 7, 2, 1, 4, 5, 3]
ShellSort(data, len(data))
print('Sorted Output:')
print(data)

Produzione:

Sorted Output:
[1, 2, 3, 4, 5, 6, 7, 8]

Applicazioni di Shell Sort

L'algoritmo Shell Sort è ancora presente nei sistemi moderni dove lo spazio di stack o la semplicità sono fattori importanti.

• Migliori Kernel Linux Utilizza Shell Sort nei punti in cui è importante evitare uno stack di chiamate.
• La libreria C integrata uClibc utilizza l'algoritmo Shell Sort per mantenere basso il consumo di memoria.
• bzip2 utilizza Shell Sort per evitare la ricorsione profonda durante l'ordinamento a blocchi.
• Il firmware integrato predilige l'algoritmo Shell Sort per insiemi di dati di piccole dimensioni in cui la ricorsione è limitata.

Vantaggi e svantaggi della selezione a guscio

Analisi della complessità di Shell Sort

Complessità temporale dell'ordinamento Shell

La complessità temporale dell'algoritmo Shell Sort dipende dalla sequenza di intervalli utilizzata.

Nel caso migliore, quando l'array è già quasi completamente disposto, ogni passaggio richiede solo un numero logaritmico di test, ovvero O(n log n).

Nel caso peggiore, l'array è organizzato in modo tale che gli elementi richiedano il massimo numero di confronti e l'incremento finale risulta dominante a O(n^2) con la sequenza originale di Shell.

1. Complessità del caso migliore: O(n log n)
2. Complessità nel caso medio: da O(n log n) a O(n^(4/3)) a seconda della sequenza degli intervalli
3. Complessità nel caso peggiore: O(n^2) con la sequenza originale di Shell

La migliore sequenza di gap per uso generale è ancora oggetto di ricerca, sebbene le sequenze di Sedgewick e Ciura offrano buone prestazioni nella pratica.

Complessità dello spazio di ordinamento delle shell

Shell Sort non richiede array ausiliari, quindi la complessità spaziale è O(1) indipendentemente dalla dimensione dell'input, il che rappresenta uno dei suoi maggiori vantaggi pratici.

DOMANDE FREQUENTI