Matematicamente.it

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?

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.

Perfetto, ho capito il problema!