Passa al tema normale
Discussioni su argomenti di Informatica

Regole del forum

Consulta il nostro regolamento e la guida per scrivere le formule
Rispondi al messaggio

[Algoritmi] Shell sort

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?

Re: [Algoritmi] Shell sort

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.

Re: [Algoritmi] Shell sort

12/09/2019, 11:13

Perfetto, ho capito il problema!
Rispondi al messaggio


Skuola.net News è una testata giornalistica iscritta al Registro degli Operatori della Comunicazione.
Registrazione: n° 20792 del 23/12/2010.
©2000— Skuola Network s.r.l. Tutti i diritti riservati. — P.I. 10404470014.