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?