Merge sort: differenze tra le versioni

Versione delle 13:48, 1 mar 2008

Versione attuale delle 11:15, 26 mar 2025

(143 versioni intermedie di 90 utenti non mostrate)

Riga 1:

{{F|programmazione|aprile 2012}}

{{S|informatica}}

{{Algoritmo

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

|classe = [[Algoritmo di ordinamento]]

|immagine = Merge-sort-example-300px.gif

|didascalia = Esempio di merge sort con una lista di numeri casuali. Innanzitutto, si divide l'elenco nell'unità più piccola (1 elemento), quindi si confronta ogni elemento con l'elenco adiacente per ordinare e unire i due elenchi adiacenti. Infine, tutti gli elementi vengono ordinati e uniti.

|struttura dati = [[Array]]

|tempo = <math>O(n\log n)</math>

|tempo migliore = <math>\Omega(n\log n)</math>

|tempo medio = <math>\Theta(n\log n)</math>

|spazio = <math>\Theta(n)</math>

|ottimale = In alcuni casi

}}

LIl 'idea''merge allasort''' baseè delun merge[[algoritmo sortdi èordinamento]] ilbasato procedimentosu 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ù piccolipiccola. 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.

== Descrizione dell'algoritmo ==

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.

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 [[Algoritmo ricorsivo|ricorsivamente]] l'algoritmo (''impera'')

# Le due sottosequenze ordinate vengono fuse (''combina''). 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 ===

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

[[File:MergeSort 2.gif|thumb|upright=2.2|Simulazione del merge sort in esecuzione su un array]]

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 agli elementi

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

==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.

A questo punto si fondono (merge) in maniera ordinata gli elementi, riunendoli in coppie:

Es. 11 => 5 e 6

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

==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.

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

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>.

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

==Esempio pratico==

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

Supponiamo di dover ordinare il seguente array:

10[0 3 151 2 13 4 9 010 15]

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.

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

<pre>

10 3

=== Implementazione ===

15 2

[[File:Merge sort algorithm diagram2.JPG|thumb|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 presentata 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]] tramite una tecnica top-down è la seguente:

1 4

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

9 0

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

</pre>

center ← (left + right) / 2

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

mergesort(a, left, center)

<pre>

mergesort(a, center+1, right)

10 3 -> 3 10

merge(a, left, center, right)

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

15 2 -> 2 15

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

1 4 -> 1 4

9 0 -> 0 9

</pre>

Al passo successivo:

<pre>

3 10 2 15 -> 2 3 10 15

1 4 0 9 -> 0 1 4 9

</pre>

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.

==[[Pseudocodice]]==

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

i ← left

j ← center + 1

k ← 0

b ← array temp size= right-left+1

while ((i <= center) && (j <= right)) do

'''while''' i ≤ center '''and''' j ≤ right '''do'''

if (a[i] <= a[j]) then

'''if''' a[i] ≤ a[j] '''then'''

b[k] ← a[i]

i ← i + 1

k ← k + 1

else

b[k] = a[j] '''else'''

jb[k] ← a[j + 1 ]

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''' (ij <=≤ center)right '''do'''

b[k] ← a[ij]

i j ← ij + 1

k ← k + 1

'''end while'''

while'''for''' (jk <=← left '''to''' right) '''do'''

b a[k] ← ab[jk-left]

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)

==Implementazioni Analisi ==

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>

Seguono alcune implementazioni in vari [[Linguaggio di programmazione|linguaggi]].

la cui soluzione in forma chiusa è <math>\Theta(n \log n)</math>, per il secondo caso del [[teorema principale]].

===[[C (linguaggio)|C]]===

<source lang="C">

#include <stdio.h>

#define LEN 8

Esistono implementazioni più efficienti della procedura merge, che hanno nel caso migliore complessità <math>O(1)</math>. Infatti, 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.

void merge(int a[], int left, int center, int right) {

int i, j, k;

int b[LEN];

== Bibliografia ==

i = left;

* {{Cita libro|autore=Thomas H. Cormen|wkautore=Thomas H. Cormen|autore2=Charles Eric Leiserson|autore3=Ronald Linn Rivest|wkautore3=Ronald Rivest|autore4=Clifford Stein|titolo=[[Introduzione agli algoritmi|Introduction to algorithms]]|edizione=3|data=2009|editore=MIT Press|ISBN=978-0-262-53305-8}}

j = center+1;

k = 0;

== Altri progetti ==

while ((i<=center) && (j<=right)) {

{{interprogetto|b=Implementazioni di algoritmi/Merge sort|b_oggetto=implementazioni|b_preposizione=del|preposizione=sul}}

if (a[i] <= a[j]) {

b[k] = a[i];

i++;

} else {

b[k] = a[j];

j++;

}

== Collegamenti esterni ==

k++;

* {{Collegamenti esterni}}

}

{{Ordinamento}}

while (i<=center) {

{{Portale|informatica}}

b[k] = a[i];

i++;

k++;

}

while (j<=right) {

b[k] = a[j];

j++;

k++;

}

for (k=left; k<=right; k++)

a[k] = b[k-left];

}

void mergesort(int a[], int left, int right) {

int center;

if(left<right) {

center = (left+right)/2;

mergesort(a, left, center);

mergesort(a, center+1, right);

merge(a, left, center, right);

}

}

int main(void) {

int a[LEN], i;

for(i=0; i<LEN; i++) {

printf(": ");

scanf("%d", &a[i]);

}

mergesort(a, 0, LEN-1);

printf("[ ");

for(i=0; i<LEN; i++)

printf("%d ", a[i]);

printf("]\n");

return 0;

}

</source>

===[[C (linguaggio)|C (metodo iterativo)]]===

[[Immagine:Merge_sort_algorithm_diagram2.JPG|thumb|Rappresentazione grafica]]

Questa particolare implementazione iterativa dell'algoritmo si basa su un principio inverso alla ricorsione, mentre molte implementazioni iterative tentano di imitare la ricorsione usando una pila che simuli lo stack delle funzioni ricorsive, questa invece effettua le operazioni matematicamente inverse a quelle effettuate dal metodo ricorsivo:

il metodo ricorsivo divide il vettore per due fino ad arrivare all'elemento più piccolo, l'unità indivisibile, dopodiché comincia a fondere i singoli elementi formando delle coppie ordinate, poi crea delle coppie di coppie e cosi via fino ad ottenere il vettore completo ed ordinato, durante queste operazioni però ci sono dei resti, cioè dei pezzi di vettore avanzati che non potevano formare delle coppie, questi nel metodo ricorsivo sono molto facili da gestire poiché vengono lasciati nello stack, e fusi al momento opportuno con il pezzo di vettore precedentemente ordinato tramite il merge.

Nel metodo iterativo puro invece essi sono più difficili da gestire, ma con la variabile sizetomerge e l'operazione %n (resto della divisione per n) si è cercato di simulare proprio questo concetto, ottenendo cosi un algoritmo che operasse come il merge sort ricorsivo, senza usare strutture d'appoggio stack per i dati.

Si Parte dall'elemento indivisibile per formare delle coppie da fondere fino a coprire l'intera dimensione del vettore.

v={3,2,5,6,1}

iterative merge sort()

ciclo

{

elementi indivisibili [3] [2] [5] [6] [1]

merge a due a due [2,3] [5,6] resto: [1] sizetomerge - 1

merge a due a due [2,3,5,6] resto: [1] se ci fossero altri resti verrebbero fusi tra di loro

}

*n è il numero di elementi unitari costituenti la coppia di cui fare il merge. es. n=2 merging [e1] whit [e2]

*merge() effettua il classico merge sul vettore di due sottovettori a e b dove a = [ v[start], v[center] ] e b = [ v[center], v[end] ]

*sizetomerge è la lunghezza del vettore da coprire con il merging delle coppie per la prossima iterazione

*sizetomerge%n è il numero di elementi che non possono essere accoppiati (il resto)

*quando dopo un iterazione ci sono elementi che non possono essere accoppiati sizetomerge decrementa per lasciarli da parte, mentre se c'era già un vecchio resto i due resti vengono fusi in modo ordinato e poi si decrementa sizetomerge per lasciarli da parte.

*alla fine il resto ordinato viene fuso con il vettore ordinato

<source lang="C">

void merge(int a[], int start, int center, int end, int size) {

int i, j, k;

int app[size];

i = start;

j = center+1;

k = 0;

while ((i<=center) && (j<=end)) {

if (a[i] <= a[j]) {

app[k++] = a[i++];

} else {

app[k++] = a[j++];

}

}

while (i<=center)

app[k++] = a[i++];

while (j<=end)

app[k++] = a[j++];

for (k=start; k<=end; k++)

a[k] = app[k-start];

printv(a,size);

// printf("merging.. {v[%d] - v[%d]} whit {v[%d] - v[%d]} \n",start,center,center+1,end);

}

void iterativemergesort(int a[],int size) {

int sizetomerge=size-1;

size--;

int i;

int n=2;

while (n<sizetomerge*2) {

for (i=0; (i+n-1)<=sizetomerge; i+=n) {

merge(a,i,(i+i+n-1)/2,i+(n-1),sizetomerge);

}

i--;

if ((sizetomerge+1)%n!=0) {

if (size>sizetomerge)

merge (a,sizetomerge -((sizetomerge)%n),sizetomerge,size,size);

sizetomerge=sizetomerge-((sizetomerge+1)%n);}

n=n*2;

}

if (size>sizetomerge)

merge (a,0,size-(size-sizetomerge),size,size);

}

//dal main chiamare iterativemergesort(vettore,dimensione del vettore);

</source>

===[[C++]]===

<source lang="cpp">

typedef int Item;

int main() {

const int n=8;

int a[n] = {10, 3, 15, 2, 1, 4, 9, 0};

mergesort(a,0,n-1);

return 0;

}

void mergesort(Item a[], int left, int right) {

if (left<right) {

int center = (left+right)/2;

mergesort(a, left, center);

mergesort(a, center+1, right);

merge(a, left, center, right);

}

}

void merge(Item a[], int left, int center, int right) {

const int n=8;

static Item aux[n];

int i,j;

for (i = center+1; i > left; i--) aux[i-1] = a[i-1];

for (j = center; j < right; j++) aux[right+center-j] = a[j+1];

for (int k = left; k <= right; k++)

if (aux[j] < aux[i]) a[k] = aux[j--];

else a[k] = aux[i++];

}

</source>

===[[Linguaggio di programmazione Java|Java]]===

<source lang="java">

import java.util.*;

public class Sort {

private static void mergeSort(int[] a, int[] vectorTemp, int left, int right) {

if (left < right) {

int center = (left + right) /2;

mergeSort (a, vectorTemp, left, center);

mergeSort (a, vectorTemp, center+1, right);

merge (a, vectorTemp, left, center+1, right);

}

}

public static void mergeSort(int[] a) {

int vectorTemp [];

vectorTemp = new int [a.length];

mergeSort (a, vectorTemp, 0, a.length-1);

}

private static void merge(int[] a, int[] vectorAux, int posLeft, int posRight, int posEnd) {

int endLeft = posRight -1;

int posAux = posLeft;

int numElemen = posEnd - posLeft +1;

while (posLeft <= endLeft && posRight <=posEnd) {

if ((a[ posLeft ])< (a[posRight]))

vectorAux [posAux++]=a[posLeft++];

else

vectorAux [posAux++] = a[posRight++];

}

while (posLeft <= endLeft)

vectorAux [posAux++]=a[posLeft++];

while (posRight <= posEnd)

vectorAux [posAux++]=a[posRight++];

for (int i=0;i<numElemen;i++,posEnd--)

a[posEnd]=vectorAux[posEnd];

}

public static void print(int[] vector) {

System.out.print("{");

for(int i=0;i<vector.length;i++) {

System.out.print(" "+vector[i]);

if(i==vector.length-1)

System.out.println(" }");

else System.out.print(",");

}

}

public static void main(String[] args) {

int vector[]= { 10, 3, 15, 2, 1, 4, 9, 0};

System.out.println("Array Non Ordinato:");

print(vector);

System.out.println();

mergeSort(vector);

System.out.println("Array Ordinato Con MergeSort:");

print(vector);

}

}

</source>

[[Categoria:Algoritmi di ordinamento]]

== Analisi delle prestazioni ==

Il tempo di esecuzione dell'algoritmo Merge Sort è [[O-grande|Θ]](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

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

che per il secondo caso del [[teorema master]] è Θ(''n''log''n'').

{{Ordinamento}}

[[cs:Merge sort]]

[[de:Mergesort]]

[[en:Merge sort]]

[[eo:Kunfanda ordigo]]

[[es:Ordenamiento por mezcla]]

[[fi:Lomituslajittelu]]

[[fr:Tri fusion]]

[[he:מיון מיזוג]]

[[id:Merge sort]]

[[ja:マージソート]]

[[lb:Mergesort]]

[[lt:Sąlajos rikiavimo algoritmas]]

[[nl:Mergesort]]

[[no:Flettesortering]]

[[pl:Sortowanie przez scalanie]]

[[pt:Merge sort]]

[[ru:Сортировка слиянием]]

[[sk:Triedenie zlučovaním]]

[[tr:Birleştirmeli sıralama]]

[[uk:Сортування злиттям]]

[[vi:Sắp xếp trộn]]

[[zh:归并排序]]