Merge sort

Da Wikipedia, l'enciclopedia libera.

Merge sort
Example of merge sort sorting a list of random dots.

Esempio di merge sort con una lista di numeri casuali.
Classe Algoritmo di ordinamento
Struttura dati Array
Caso pessimo temporalmente Θ(nlogn)
Caso ottimo temporalmente Θ(nlogn)
Caso medio temporalmente Θ(nlogn)
Caso pessimo spazialmente Θ(n)
Ottimale In alcuni casi
Questo box: vedi • disc. • mod.

Il merge sort è un algoritmo di ordinamento molto intuitivo e abbastanza rapido, che utilizza un processo di risoluzione ricorsivo.

L'idea alla base del merge sort è il procedimento Divide et Impera, che consiste nella suddivisione del problema in sottoproblemi via via più piccoli.

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.

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

Indice

[modifica] Fase 1: Divide

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 meno del secondo.

Es. 11 => 5 e 6

[modifica] Fase 2: Impera

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

Dati un array A e due indici x ≤ y, denotiamo A[x;y] la porzione dell'array A costituita dagli elementi A[x]...A[y].

[modifica] 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:

10 3

15 2

 1 4

 9 0

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

10 3 -> 3 10

15 2 -> 2 15

 1 4 -> 1  4

 9 0 -> 0  9

Al passo successivo:

3 10 2 15 -> 2 3 10 15

1  4 0  9 -> 0 1  4  9

Infine:

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

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.

[modifica] Modalità di implementazione

Esistono vari tipi di implementazione del mergesort.

[modifica] 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

[modifica] 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 2 
9 4
0

Terzo passo, continuo ad unire le sequenze due a due

2 3 10 15
1 2 4 9
0

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

1 2 2 3 4 9 10 15
0

0 1 2 2 3 4 9 10 15

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

[modifica] Pseudocodice

 merge (a[], left, center, right)  
    i ← left
    j ← center + 1
    k ← 0
 
    while ((i <= center) && (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)

[modifica] Analisi delle prestazioni

Il tempo di esecuzione dell'algoritmo Merge Sort è Θ(n log n). Infatti:

- la funzione merge 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

T(n) = 2T\left(\frac{n}{2}\right)+ \Theta(n)

che per il secondo caso del teorema master è Θ(nlogn).

Da notare che questa complessità si mantiene tale in ogni caso, da quello migliore a quello peggiore, ed è questo uno dei punti di forza dell'algoritmo.

[modifica] Altri progetti

Estratto da "http://it.wikipedia.org/wiki/Merge_sort"
Strumenti personali