Discussione:Merge sort

	Questa voce rientra tra gli argomenti trattati dal progetto tematico sottoindicato. Puoi consultare le discussioni in corso, aprirne una nuova o segnalarne una avviata qui.
Informatica bar di progetto monitoraggio voci

	La voce è stata monitorata per definirne lo stato e aiutarne lo sviluppo. Ha ottenuto una valutazione di livello minimo (aprile 2012).
C Seri problemi relativi all'accuratezza dei contenuti. Importanti aspetti del tema non sono trattati o solo superficialmente. Altri aspetti non sono direttamente attinenti. Alcune informazioni importanti risultano controverse. Potrebbero essere presenti uno o più avvisi. (che significa?) C Seri problemi di scrittura. Linguaggio comprensibile, ma con stile poco scorrevole. Strutturazione in paragrafi carente. (che significa?) E Gravissimi problemi relativi alla verificabilità della voce. Fonti assenti o del tutto inadeguate. Presenza o necessità del template {{F}}. (che significa?) B Lievi problemi relativi alla dotazione di immagini e altri supporti grafici nella voce. Mancano alcuni file o altri sono inadeguati. (che significa?)
Monitoraggio effettuato nell'aprile 2012

Implementazioni

Ricordo a tutti che le implementazioni in specifici linguaggi vanno messe su Wikibooks, come da decisione della comunità. Il link a wikibooks è in fondo alla voce, nella sezione Altri progetti. Grazie. --Giuseppe (msg) 16:43, 27 gen 2010 (CET)

Complessità computazionale del mergesort

Scrivi che la complessità computazionale è costante,ma invece è uguale a n nel caso migliore , e nlogn nel caso peggiore. Perchè durante la procedura di merge, supponiamo di avere 2 array ognuno di dimensione n/2, se il primo array contiene elementi tutti quanti più piccoli del primo array, allora bisogna effettuare n/2 confronti, e l' array riunito avrà nella prima metà tutti gli elementi del primo sub-array, ma gli elementi della seconda metà si copiano uguali a quelli del secondo sub-aray, senza stare a confrontarli. Nel caso peggiore cioè un array del tipo 1 3 5 7 2 4 6 allora si che ha complessità uguale a nlogn.Ma non è un costo costante. — Questo commento senza la firma utente è stato inserito da 79.21.182.8 (discussioni · contributi).

Ho annullato la modifica, era corretto prima. Il fatto che la complessità dell'algoritmo sia Θ(n log n) per qualunque distribuzione degli input dipende da due fatti:

1. La complessita della procedura merge è Θ(n).
2. La profondità della ricorsione della procedura mergesort è Θ(log n).

Ad esempio, se l'array in input fosse 1 2 3 4 5 6 7 8, l'albero di ricorsione sarebbe (elenco livello per livello):

1. mergesort([1, 2, 3, 4, 5, 6, 7, 8])
2. mergesort([1, 2, 3, 4]) e mergesort([5, 6, 7, 8]), con 1 merge che effettua ~4 confronti
3. mergesort([1, 2]) mergesort([3, 4]), mergesort([5, 6]), mergesort([7, 8]), con 2 merge che effettuano ciascuno ~2 confronti
4. mergesort([1]), mergesort([2]), mergesort([3]), mergesort([4]), mergesort([5]), mergesort([6]), mergesort([7]), mergesort([8]), con 4 merge che effettuano ciascuno ~1 confronto.

Come vedi, a parte la chiamata iniziale, ci sono esettamente 3 = log 8 livelli, e ad ogni livello il numero totale di confronti è sempre Θ(n). Ciao, Salvatore Ingala (conversami) 09:21, 23 ott 2011 (CEST)

Nel caso dell' array già ordinato, ci vogliono n-1 confronti per verificare che è già ordinato. Supponiamo di avere {1,2,3,4,5,6,7,8}. Dopo averlo diviso in 4 array mi servono 4 confronti per avere 4 array ordinati: {1,2} {3,4} {5,6} {7,8} Da questi 4 array mi servono 2 confronti per ottenerne 2 ordinati (confronto 2 con 3 e 6 con 7), e ottengo {1,2,3,4} e {5,6,7,8}.Ora da questi due vettori, per ottenerne uno unico ordinato mi basta 1 confronto: so che 4 è più piccolo di 5 quindi non vado avanti a confrontare tutti gli altri elementi. Con 7 confronti ho ordinato l' array.

Comodo non rispondere e non cambiare però il contenuto, quando tutti sanno che nel caso migliore il mergesort ha complessità O(n). — Questo commento senza la firma utente è stato inserito da 79.0.188.217 (discussioni · contributi).

Mi scuso per non aver risposto prima, ma in questi giorni sono stato impegnato e la cosa mi era totalmente passata di mente; soprassiedo sul tuo insulto, che ho rimosso dalla pagina. Ho approfondito un po' la faccenda, e il tuo ragionamento è corretto; il problema è che tu hai fatto questo ragionamento senza considerare l'implementazione in pseudocodice dell'algoritmo merge presentata nella voce, mentre io mi rifacevo a quella; la merge si può implementare in vari modi, e il modo descritto nella voce non è in grado di sfruttare il caso fortunato dell'array totalmente ordinato. Basta notare che la procedura merge si conclude con un "for k ← left to right do...", che da solo ha già un costo uguale a Θ(n). Un'implementazione più intelligente (come quella che c'è nell'analoga voce su en:wiki) avrebbe la proprietà che tu dici. Modifico il tuo testo per chiarire questo fatto, anche se sarebbe ancora meglio approfondire tutta la voce, aggiungendo dei cenni alle diverse implementazioni possibili; il testo su en.wiki potrebbe essere un'ottima base, se ti va di lavorarci. Ciao, Salvatore Ingala (conversami) 20:26, 29 ott 2011 (CEST)

Revisione voce

Ho rivisto un po' la voce. Sostanzialmente, ho

• sistemato la formattazione del primo esempio e tolto il secondo (non è molto chiaro, soprattutto perché la differenza sostanziale tra top-down e bottom-up è 'sottintesa' nel prmo esempio, e i due esempi sembravano almeno a una prima lettura uguali)
• cambiato\adattato la spiegazione del funzionamento (prendendo _molto_ spunto da en:wiki)
• messo un po' di formattazione nello pseudocodice (parole chiave in grassetto, tolto le parentesi, usato and invece che && come operatore booleano)
• sistemate\toccate alcune cose qua e la' --80.116.54.220 (msg) 23:50, 22 dic 2011 (CET)