Merge sort: differenze tra le versioni

Versione delle 11:55, 24 ott 2020

Versione attuale delle 12:15, 26 mar 2025

(18 versioni intermedie di 9 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

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