MERGESORT - qualcuno mlo spiega?

[thefrog]

come da titolo.....qualcuno mi spiega come funziona l'algoritmo mergesort???

grazie mille

[bizzu]

Allora, il ms si basa sulla tecnica "divide et impera", che consiste nel dividere il problema in più sottoproblemi, per poi risolverli ricorsivamente con la stessa tecnica; infine si combinano le soluzioni dei sottoproblemi per trovare quella del problema originario.
Quindi: tu hai un vettore, lo dividi in 2, le parti ottenute le dividi in 2, e così via ricorsivamente fino a che non hai ottenuto elementi singoli, che per definizione sono vettori ordinati; a questo punto usi la funzione di merge che, per ordinare due vettori, prende il più piccolo dei due elementi affioranti e lo inserisce nel vettore in costruzione, fino a che i due vettori di partenza non sono svuotati.
In questo modo la soluzione si "crea" a partire dal fondo (come in tutti gli algoritmi ricorsivi), fino ad arrivare al vettore originario che sarà così ordinato.

[thefrog]

Originariamente inviato da bizzu
Allora, il ms si basa sulla tecnica "divide et impera", che consiste nel dividere il problema in più sottoproblemi, per poi risolverli ricorsivamente con la stessa tecnica; infine si combinano le soluzioni dei sottoproblemi per trovare quella del problema originario.
Quindi: tu hai un vettore, lo dividi in 2, le parti ottenute le dividi in 2, e così via ricorsivamente fino a che non hai ottenuto elementi singoli, che per definizione sono vettori ordinati; a questo punto usi la funzione di merge che, per ordinare due vettori, prende il più piccolo dei due elementi affioranti e lo inserisce nel vettore in costruzione, fino a che i due vettori di partenza non sono svuotati.
In questo modo la soluzione si "crea" a partire dal fondo (come in tutti gli algoritmi ricorsivi), fino ad arrivare al vettore originario che sarà così ordinato.

grazie mille!!!


si può chiudere

[maxithron]

Aspe'!! che ora viene il bello....visto che lo squisito bizzu si è preso la briga di spiegartelo....io, volendo fare un pò il cattivello ti darò da fare gli esercizi!!!

[thefrog]

Originariamente inviato da maxithron
Aspe'!! che ora viene il bello....visto che lo squisito bizzu si è preso la briga di spiegartelo....io, volendo fare un pò il cattivello ti darò da fare gli esercizi!!!

ne ho già abbastanza grazie

[VegetaSSJ5]

Originariamente inviato da maxithron
Aspe'!! che ora viene il bello....visto che lo squisito bizzu si è preso la briga di spiegartelo....io, volendo fare un pò il cattivello ti darò da fare gli esercizi!!!

postali lo stesso...