Non funziona per vettori di dimensione dispari, e non funzionerebbe neanche escludendo l’ultimo elemento per ordinarlo a parte, tipo per dimensione 7.. chissà come si farà in quel caso
@@Algoritmi01 riferendomi all’ultima slide sul merge sort sequenziale vedo che lung è costane e non dipende dal numero di elementi del vettore, quindi mi pare (se non mi confondo) che nel caso ad esempio di una lista di 7 elementi, nell’ultimo step dove dovrebbe unire il vettore da 4 con quello da 3, siccome lung è 4 non entra nel loop per fare l’ultimo step, essendo 2lung > 7, lasciando la lista non ordinata del tutto.
Nel caso di un vettore di 7, si farà prima lo step lung 1 ( andrai a fondere i vettori da 1 a due a due, e un vettore rimane solo) poi step con lung 2 ( andrai a fondere i primi due vettori di lunghezza 2 e poi fondi un vettore di lunghezza 2 con uno di lunghezza 1) . Infine c’è lo step di lung 4 e proprio in quest’ultimo step stiamo considerando il vettore di 4 e il vettore di 3 che attraverso la fusione ottiene il vettore completo ordinato. È un po’ complicato da spiegare così ma credo che ripercorrendo i tre step ti dovrebbe tornare.
Non capisco perché la mia professoressa lo implementa in questo modo:
def mergeSortIter(A)
lung=1
while lung
Non funziona per vettori di dimensione dispari, e non funzionerebbe neanche escludendo l’ultimo elemento per ordinarlo a parte, tipo per dimensione 7.. chissà come si farà in quel caso
L’algoritmo é generico, e va bene anche per dimensioni dispari ma magari in questi casi capita di avere fusioni tra vettori con dimensioni differenti.
@@Algoritmi01 riferendomi all’ultima slide sul merge sort sequenziale vedo che lung è costane e non dipende dal numero di elementi del vettore, quindi mi pare (se non mi confondo) che nel caso ad esempio di una lista di 7 elementi, nell’ultimo step dove dovrebbe unire il vettore da 4 con quello da 3, siccome lung è 4 non entra nel loop per fare l’ultimo step, essendo 2lung > 7, lasciando la lista non ordinata del tutto.
Nel caso di un vettore di 7, si farà prima lo step lung 1 ( andrai a fondere i vettori da 1 a due a due, e un vettore rimane solo) poi step con lung 2 ( andrai a fondere i primi due vettori di lunghezza 2 e poi fondi un vettore di lunghezza 2 con uno di lunghezza 1) . Infine c’è lo step di lung 4 e proprio in quest’ultimo step stiamo considerando il vettore di 4 e il vettore di 3 che attraverso la fusione ottiene il vettore completo ordinato. È un po’ complicato da spiegare così ma credo che ripercorrendo i tre step ti dovrebbe tornare.
Ma per caso hai studiato Matematica a La Sapienza?
Ciao, ho studiato Informatica alla Sapienza 😊