Merge sort: differenze tra le versioni

Versione delle 20:09, 25 mar 2015

Versione attuale delle 12:15, 26 mar 2025

(31 versioni intermedie di 21 utenti non mostrate)

Riga 1:

{{F|programmazione|aprile 2012}}

{{Algoritmo

|classclasse = [[Algoritmo di ordinamento]]

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

|image=[[File:Merge sort animation2.gif|none|300px|Esempio di merge sort con una lista di numeri casuali.]]

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

|caption=Esempio di merge sort con una lista di numeri casuali.

|datastruttura dati = [[Array]]

|timetempo = <math>\ThetaO(n\log n)</math>

|best-timetempo migliore = <math>\ThetaOmega(n\log n)</math>

|average-timetempo medio = <math>\Theta(n\log n)</math>

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

|optimalottimale = In alcuni casi

}}

Riga 18:

# 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 [[RicorsioneAlgoritmo 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 ===

[[File:AnimazioneMergeSortMergeSort 2.gif|thumb|upright=2.2|Simulazione del merge sort in esecuzione su di 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 alleagli coppieelementi

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

A questo punto si fondono (merge) in maniera ordinata gli elementi, riunendoriunendoli lein metàcoppie:

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

Riga 40:

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.

=== Implementazione ===

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

Riga 57 ⟶ 58:

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

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

i ← left

j ← center + 1

k ← left0

b ← array temp size= right-left+1

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

Riga 68:

b[k] ← a[i]

i ← i + 1

k ← k + 1

'''else'''

b[k] ← a[j]

j ← j + 1

k ← k + 1

'''end while'''

Riga 87 ⟶ 88:

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

a[k] ← b[k-left]

a[k] ← b[k]

== Analisi ==

Riga 97 ⟶ 98:

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

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

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.

== Bibliografia ==

* {{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}}

* {{cita libro| Thomas | Cormen | Introduction to Algorithms | ed=3 }}

== Altri progetti ==

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

== Collegamenti esterni ==

* {{Collegamenti esterni}}

{{Ordinamento}}

{{Portale|informatica}}

[[Categoria:Algoritmi di ordinamento]]