Merge sort: differenze tra le versioni

Versione delle 17:43, 28 nov 2011

Versione delle 00:49, 23 dic 2011

Riga 12:

|optimal=In alcuni casi

}}

[[Immagine:AnimazioneMergeSort.gif|thumb|right|492px|Simulazione del merge sort in esecuzione su di un array]]

Il '''merge sort''' è un [[algoritmo]] [[algoritmo di ordinamento|di ordinamento]] abbastanza rapido che utilizza un processo di risoluzione [[Algoritmo ricorsivo|ricorsivo]].

[[File:Merge sort algorithm diagram2.JPG|thumb|250px|left|Raffigurazione grafica delle versioni iterativa e ricorsiva dell'algoritmo merge sort.]]

L'idea alla base del merge sort è il procedimento [[Divide et impera (informatica)|Divide et Impera]], che consiste nella suddivisione del problema in sottoproblemi via via più piccoli.

Il '''merge sort''' è un [[algoritmo]] [[algoritmo di ordinamento|di ordinamento]] basato su confronti che utilizza un processo di risoluzione [[Algoritmo ricorsivo|ricorsivo]], sfruttando la tecnica del [[Divide et impera (informatica)|Divide et Impera]], che consiste nella suddivisione del problema in sottoproblemi della stessa natura di dimensione via via più piccola. Fu inventato da [[John von Neumann]] nel [[1945]]. Una descrizione dettagliata e un'analisi della versione bottom-up dell'algoritmo apparve in un articolo di Goldstine e Neumann già nel 1948.

Il merge sort opera quindi dividendo l'insieme da ordinare in due metà e procedendo all'ordinamento delle medesime ricorsivamente. Quando si sono divise tutte le metà si procede alla loro fusione (merge appunto) costruendo un insieme ordinato.

== Descrizione dell'algoritmo ==

L'algoritmo fu inventato da [[John von Neumann]] nel [[1945]].

Concettualmente, l'algoritmo funziona nel seguente modo:

# Se la sequenza da ordinare ha lunghezza 0 oppure 1, è già ordinata. Altrimenti:

# La sequenza viene divisa (''divide'') in due metà (se la sequenza contiene un numero dispari di elementi, viene divisa in due sottosequenze di cui la prima ha un elemento in più della seconda)

# Ognuna di queste sottosequenze viene ordinata, applicando [[Ricorsione|ricorsivamente]] l'algoritmo

# Le due sottosequenze ordinate vengono fuse (''impera''). Per fare questo, si estrae ripetutamente il minimo delle due sottosequenze e lo si pone nella sequenza in uscita, che risulterà ordinata

=== Esempio di funzionamento ===

==Fase 1: Divide==

[[Immagine:AnimazioneMergeSort.gif|thumb|left|492px|Simulazione del merge sort in esecuzione su di un array]]

L'insieme di elementi viene diviso in 2 metà. Se l'insieme è composto da un numero dispari di elementi, viene diviso in 2 sottogruppi dei quali il primo ha un elemento in più del secondo.

Supponendo di dover ordinare la sequenza [10 3 15 2 1 4 9 0], l'algoritmo procede ricorsivamente dividendola in metà successive, fino ad arrivare alle coppie

[10 3] [15 2] [1 4] [9 0]

Es. 11 => 6 e 5

==Fase 2: Impera==

Supponendo di avere due sequenze già ordinate, per unirle, l'algoritmo merge sort estrae ripetutamente il minimo delle due sequenze in ingresso e lo pone in una sequenza in uscita.

Dati un array <math>\mathit{A}</math> e due indici x ≤ y, denotiamo <math>\mathit{A[x;y]}</math> la porzione dell'array A costituita dagli elementi <math>\mathit{A[x]...A[y]}</math>.

==Esempio pratico==

Supponiamo di dover ordinare il seguente array:

10 3 15 2 1 4 9 0

Si procede dividendolo in metà successive, fino ad arrivare a coppie:

<pre>

10 3

15 2

1 4

9 0

</pre>

A questo punto si fondono (merge) in maniera ordinata gli elementi, riunendo le metà:

<pre>

10 3 -> 3 10

[3 10] [2 15] [1 4] [0 9]

15 2 -> 2 15

Al passo successivo, si fondono le coppie di array di due elementi:

1 4 -> 1 4

9[2 03 ->10 15] [0 1 4 9]

</pre>

Al passo successivo:

<pre>

Infine, fondendo le due sequenze di quattro elementi, si ottiene la sequenza ordinata:

3 10 2 15 -> 2 3 10 15

[0 1 2 3 4 0 9 ->10 0 1 4 915]

</pre>

Infine:

L'esecuzione ricorsiva all'interno del calcolatore non avviene nell'ordine descritto sopra. Tuttavia, si è formulato l'esempio in questo modo per renderlo più comprensibile.

2 3 10 15 0 1 4 9 -> 0 1 2 3 4 9 10 15

=== Implementazione ===

[[File:Merge sort algorithm diagram2.JPG|thumb|250px|right|Raffigurazione grafica delle versioni iterativa (bottom-up) e ricorsiva (top-down) dell'algoritmo]]

L'algoritmo può essere implementato fondamentalmente tramite due tecniche:

# '''Top-Down''', che è quella presentanto in questa pagina. Opera da un insieme <math>A</math> e lo divide in sotto insiemi <math>(A_1, A_2)</math> fino ad arrivare all'insieme contenente un solo elemento, per poi riunire le parti scomposte;

# '''Bottom-Up''', che consiste nel considerare l'insieme <math>A</math> come composto da un vettore di <math>n</math> sequenze. Ad ogni passo vengono fuse due sequenze.

Una possibile implementazione dell'algoritmo in forma di [[Pseudocodice|pseudocodice]] tramite una tecnica top-down è la seguente:

L'esecuzione ricorsiva all'interno del calcolatore non avviene nell'ordine descritto sopra, ma si è preferito formulare l'esempio in questo modo in maniera da renderlo più comprensibile.

'''function''' mergesort (a[], left, right)

== Modalità di implementazione ==

'''if''' left < right '''then'''

center ← (left + right) / 2

mergesort(a, left, center)

mergesort(a, center+1, right)

merge(a, left, center, right)

Una possibile implementazione della funzione merge (unione di due sottosequenze ordinate) è la seguente:

Esistono vari tipi di implementazione del mergesort.

'''function''' merge (a[], left, center, right)

=== Metodo Top-Down ===

Corrisponde a quello presentanto in questa pagina, che opera da un insieme A e lo divide in sotto insiemi (A1, A2) fino ad arrivare all'unità per poi riunire le parti scomposte

=== Metodo Bottom-Up ===

Consiste nel considerare l'insieme A come composto da un vettore di n sequenze. Ad ogni passo fondo insieme due sequenze.

Riproponendo l'esempio sopra la sequenza dei passi diventa:

10 3 15 2 1 4 9 0

Primo passo, ho n sequenze distinte:

10

3

15

2

1

4

9

0

Secondo passo, unisco le sequenze due a due:.

3 10

2 15

1 4

0 9

Terzo passo, continuo ad unire le sequenze due a due

2 3 10 15

0 1 4 9

Ho ancora più di una sequenza diversa, quindi continuo ad unire

0 1 2 3 4 9 10 15

a questo punto è rimasta una sola sequenza che è quella finale

==[[Pseudocodice]]==

merge (a[], left, center, right)

i ← left

j ← center + 1

k ← 0

'''while''' ((i <=≤ center) &&'''and''' (j <=≤ right)) '''do'''

'''if''' (a[i] <=≤ a[j])

'''then'''

b[k] ← a[i]

i ← i + 1

'''else'''

b[k] ← a[j]

j ← j + 1

k ← k + 1

'''end while'''

'''while''' (i <=≤ center) '''do'''

b[k] ← a[i]

i ← i + 1

k ← k + 1

'''end while'''

'''while''' (j <=≤ right) '''do'''

b[k] ← a[j]

j ← j + 1

k ← k + 1

'''end while'''

'''for''' k ← left '''to''' right '''do'''

a[k] ← b[k - left]

mergesort (a[], left, right)

if (left < right) then

center ← (left + right) / 2

mergesort(a, left, center)

mergesort(a, center+1, right)

merge(a, left, center, right)

== Analisi delle prestazioni ==

Il tempo di esecuzione dell'algoritmo Merge Sort è [[Stima asintotica#Relazione Theta .CE.98|Θ]](n log n). Infatti:

== Analisi ==

- la funzione merge qui presentata ha costo Θ(n), e mergesort richiama se stessa due volte ogni volta su metà della porzione di input. Quindi possiamo associare al tempo di esecuzione di mergesort la funzione temporale

L'algoritmo Merge Sort, per ordinare una sequenza di <math>n</math> oggetti, ha complessità temporale <math>T(n) = \Theta(n\log n)</math> sia nel caso medio che nel caso pessimo. Infatti:

* la funzione merge qui presentata ha complessità temporale <math>\Theta(n)</math>

* mergesort richiama se stessa due volte, e ogni volta su (circa) metà della sequenza in input

Da questo segue che il tempo di esecuzione dell'algoritmo è dato dalla ricorrenza

<math>T(n) = 2T\left(\frac{n}{2}\right)+ \Theta(n)</math>

chela cui soluzione in forma chiusa è <math>\Theta(n \log n)</math>, per il secondo caso del [[Teorema_principale_(informatica)|teorema masterprincipale]] è Θ(''n''log''n'').

Esistono implementazioni più efficienti della procedura merge, che hanno nel caso migliore complessità <math>O(1);</math>. infattiInfatti, se i due array da fondere sono già ordinati, è sufficiente confrontare l'ultimo elemento del primo array con il primo elemento del secondo array per sapere che si può fonderli senza effettuare ulteriori confronti. Per cui si può implementare l'algoritmo mergesort in modo che abbia complessità O(nlogn) nel caso peggiore, e O(n) nel caso migliore, cioè quando l'array è già ordinato.

== Altri progetti ==