Merge sort: differenze tra le versioni

Versione delle 14:32, 6 nov 2019

Versione attuale delle 12:15, 26 mar 2025

(19 versioni intermedie di 10 utenti non mostrate)

Riga 2:

{{Algoritmo

|classe = [[Algoritmo di ordinamento]]

|immagine = Merge -sort animation2-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>\ThetaO(n\log n)</math>

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

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

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

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

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 102 ⟶ 103:

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