Shell Sort in Python
L'algoritmo ShellSort è un algoritmo di ordinamento che generalizza l'algoritmo di Insertion Sort. L'ordinamento avviene mediante il confronto tra coppie di elementi iterando il procedimento.
Cosa trovi in questo video
L'algoritmo ShellSort è un algoritmo di ordinamento che generalizza l'algoritmo di Insertion Sort. L'ordinamento avviene mediante il confronto tra coppie di elementi iterando il procedimento.
Questo video accompagna la guida Shell Sort in Python e riprende i passaggi principali con una spiegazione più diretta e visuale.
Sintesi del video
L’algoritmo ShellSort è un algoritmo di ordinamento che generalizza l’algoritmo di Insertion Sort. L’ordinamento avviene mediante il confronto tra coppie di elementi iterando il procedimento.
Punti trattati
- Strategia di ordinamento
- Primo ciclo N/2
- Secondo ciclo N/4
- Terzo ciclo N/8
- Implementazione (in Python)
Testo di supporto
In questo articolo, imparerai le nozioni alla base dell’algoritmo e vedrai una sua implementazione nel linguaggio Python.
L’algoritmo Shell Sort è un algoritmo di ordinamento che generalizza l’algoritmo Insertion Sort. L’algoritmo prevede l’ordinamento di coppie di elementi distanziati di un certo numero di elementi, iterando tale approccio (a ritroso) fino al completo ordinamento dell’elenco dati iniziale.
L’intervallo di elementi utilizzato, attraverso il quale si procede
all’ordinamento, dipende dalla sequenza usata. La sequenza standard utilizzata
dall’algoritmo prevede come intervalli: N/2, N/4, N/8, …, 1.
Da notare che le prestazioni dell’algoritmo dipendono dal tipo di sequenza utilizzata per una dato input di dati.
Ipotiziammo l’utilizzo della sequenza standard, e quindi divideremo il nostro
elenco in intervalli: N/2, N/4, …, 1.
Nel primo ciclo la sequenza ha dimensione N=8, l’algoritmo prende come
intervallo N/2 = 4 e quindi gli elementi sono comparati a coppie di distanza
pari a 4 eseguendo le seguenti iterazioni.
Ogni comparazione prevede lo spostamento degli elementi; si ha una spostamento, se l’elemento con indice inferiore risulta essere maggiore dell’elemento con indice maggiore.
Il secondo ciclo prevede un intervallo pari a N/4 = 8/4 = 2. Le iterazioni in
questo intervallo sono:
Nella successiva iterazione N/8 = 8/8 = 1 sono comparati gli elementi vicini
per ordinare tutti gli elementi:
| Caso | Complessità |
|---|---|
| Migliore | O(n log n) |
| Medio | O(n log n) |
| Peggiore | O(n²) |
Approfondimento scritto
Per comandi, esempi e passaggi completi puoi leggere l’articolo collegato: Shell Sort in Python .
Come continuare
Se vuoi riprendere il contenuto con calma, puoi rivedere il video su YouTube o usare l'articolo scritto come riferimento testuale.