Merge sort: differenze tra le versioni

Versione delle 19:46, 11 mag 2021

Versione attuale delle 12:15, 26 mar 2025

(14 versioni intermedie di 5 utenti non mostrate)

Riga 2:

{{Algoritmo

|classe = [[Algoritmo di ordinamento]]

|immagine = Merd 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 12:

}}

Il '''merdmerge sort''' è un [[algoritmo di ordinamento]] basato su 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ù piccola. 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 ==

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 90 ⟶ 91:

== Analisi ==

L'algoritmo MerdMerge 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

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