PDA

Visualizza la versione completa : Merge-sort


kk.87
27-06-2008, 13:09
Chi saprebbe spiegarmi in parole povere come funziona il merge sort? continuo a nn capirlo

LexLex
27-06-2008, 23:58
Ciao,
Merge Sort è un algoritmo divide et impera,
sicuramente non riuscirò a spiegartelo meglio di wikipedia (che ti consiglio di visitare) qui (http://en.wikipedia.org/wiki/Merge_sort) ,

in parole poverissime,

Dividendo più volte in due l'insieme da ordinare (virtualmente si intende)
arrivi al caso limite di (n) insiemi di un elemento (che quindi banalmente sono gia ordinati!),

L'ordinamento vero e proprio inizia adesso con il merge (in italiano fusione),
di quei sottoinsiemi che hai creato, quindi unisci due insiemi, e lo fai in maniera ordinata attraverso il confronto. Parti proprio dagli insiemi di un elemento
ed ordini ad ogni passo un sottoinsieme più grande,
risalendo verso il numero (n) di elementi dell'insieme.

http://forum.html.it/forum/faccine/018.gif
Spero di essere stato chiaro.
Ciao

menphisx
28-06-2008, 00:08
Dividi fino a quando ottieni due insiemi di 1 elemento.
Prendi il minore del primo insieme e il minore del secondo.
Metti il minore dei due in cima e l'altro come secondo.
Così ottieni un nuovo insieme ordinato.
Ripeti la procedura con due insiemi da due, poi con due insiemi da 4, e man mano gli insiemi saranno ordinati, fino ad ottenere l'ultimo insieme ordinato.

http://upload.wikimedia.org/wikipedia/en/thumb/e/e6/Merge_sort_algorithm_diagram.svg/618px-Merge_sort_algorithm_diagram.svg.png

Loading