[Algoritmi] Shell sort

Messaggioda ZfreS » 11/09/2019, 11:11

Sto studiando l'algoritmo di shell sort, ma ho difficoltà a capire una parte.
Supponiamo di avere un vettore di numeri:
Codice:
 v[5, 2, 7, 9, 4, 11, 3, 1]

In base a ciò che ho letto viene calcolato un intervallo di valori, in questo caso $4$ e poi vengono presi valori da ordinare a distanza di 4. Quindi in questo caso viene confrontato il $5$ con il $4$ e vengono scambiati, poi il 2$ con $11$ poi $7$ con $3$ e vengono scambiati e infine il $9$ con $1$.Ora il vettore è questo:
Codice:
 v[4, 2, 3, 1, 5, 11, 7, 9]
Finito il primo ciclo l'intervallo si dimezza diventando $2$. Ora vengono confrontati il $4$ con il $3$ e vengono scambiati, poi il $2$ con $1$ e vengono scambiati, poi il $4$ con $5$ poi il $2$ con $11$, il $5$ con il $7$ e infine l'$11$ col $9$ che vengono scambiati. L'array ottenuto è:
Codice:
 v[3, 1, 4, 2, 5, 9, 7, 11]
. Ora l'intervallo si dimezza e a quanto ho capito l'algoritmo si riduce all'insertion sort dato che l'intervallo è diventato 1. Ma allora ciò che ho fatto fin ora non era l'insertion sort? Poi ho visto vari video, ma ragionavano tutti in modo diverso. Potreste spiegarmi questa parte?
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1804 di 4589
Iscritto il: 22/10/2016, 17:52

Re: [Algoritmi] Shell sort

Messaggioda apatriarca » 12/09/2019, 01:37

Nell'insertion sort scambi solo valori adiacenti. Scambi infatti sempre il valore alla fine dell'array con ogni valore più basso che lo precede. Conviene pensare di dividere l'array in gruppi con indici del tipo \(k\,i + s\) dove \(k\) è la distanza tra i valori e \(s < k\) è l'indice di partenza. Esegui quindi l'insertion sort su ognuno di questi gruppi in modo indipendente per poi passare al valore di \(k\) successivo.
apatriarca
Moderatore
Moderatore
 
Messaggio: 5294 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Algoritmi] Shell sort

Messaggioda ZfreS » 12/09/2019, 11:13

Perfetto, ho capito il problema!
ZfreS
Cannot live without
Cannot live without
 
Messaggio: 1805 di 4589
Iscritto il: 22/10/2016, 17:52


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite