Guida Merge sort

[ptm]

Algoritmi di ordinamento -> Merge sort

Il Merge sort è un algoritmo di ordinamento di tipo "divide et impera" ricorsivo inventato nel 1945 da John von Neumann e presenta una complessità di O(n log n). Una procedura di tipo Divide et impera si preoccupa inizialmente di suddividere il problema iniziale in diversi sottoproblemi della stessa natura di dimensione più piccola. Rispetto agli altri algoritmi visti finora, questo rientra a far parte di quelli efficienti (anche se non non dimostreremo il perchè la complessità è O(n log n)).

Concettualmente il merge sort consta di due operazioni:

1. Suddivisione della lista disordinata in n sottoliste, ciascuna contenente un solo elemento (una lista con un solo elemento è di per sè ordinata)
2. Unione (merge) delle sottoliste ordinate in modo da ottenere ancora una lista ordinata; questa operazione viene ripetuta finchè non si ottiene una sola sottolista (che sarà quindi quella di partenza ordinata)

Nella figura è possibile osservare l'animazione dell'algoritmo

Codice (C++)

Una possibile implementazione del merge sort è quella che segue. Come al solito sono presenti alcuni commenti accanto alle parti più importanti

Perfavore, Entra oppure Registrati per vedere i codici!

e un esempio di utilizzo

Perfavore, Entra oppure Registrati per vedere i codici!

N.B. : è di facile costruzione la variante in C. L'unica modifica da fare è la sostituzione di new e delete con malloc() e free().

 

[Hew0x]

@ptm , hai tralasciato alcune cose:
Si dice che quicksort è molto meglio di mergesort ... Quicksort ha un O(n^2) caso peggiore di runtime e O(nlogn) ha un medio caso di runtime.
E' superiore a merge sort in molti scenari perchè molti fattori influenzano un runtime dell'algoritmo, e ovviamente merge sort perde.
Quicksort richiede poco spazio e presenta una buona frazione di cache, e questo lo rende più veloce di merge sort in molti casi.
Parlando di altre cose, come località di riferimento anche azionano un ruolo importante sull'hardware corrente.
Specificamente, il runtime citata di algoritmi di ordinamento si riferisce al numero di confronti o il numero di swap necessari per eseguire da ordinare i dati. Si, questa è una buona misura della prestazione, perché è indipendente dalla progettazione hardware sottostante.

 

[ptm]

@ptm , hai tralasciato alcune cose:
Si dice che quicksort è molto meglio di mergesort ... Quicksort ha un O(n^2) caso peggiore di runtime e O(nlogn) ha un medio caso di runtime.
E' superiore a merge sort in molti scenari perchè molti fattori influenzano un runtime dell'algoritmo, e ovviamente merge sort perde.
Quicksort richiede poco spazio e presenta una buona frazione di cache, e questo lo rende più veloce di merge sort in molti casi.
Parlando di altre cose, come località di riferimento anche azionano un ruolo importante sull'hardware corrente.
Specificamente, il runtime citata di algoritmi di ordinamento si riferisce al numero di confronti o il numero di swap necessari per eseguire da ordinare i dati. Si, questa è una buona misura della prestazione, perché è indipendente dalla progettazione hardware sottostante.

In verità non ho parlato di quicksort perchè questa discussione si riferisce esclusivamente all'algoritmo mergesort... riguardo alla misura della prestazione normalmente non ci si riferisce nello specifico al numero di swap o di confronti, ma la notazione O-grande è utilizzata per descrivere il comportamento asintotico della funzione (in pratica se dico O(n log n) non significa che ho esattamente in media n log n swap)

 

[Hew0x]

In verità non ho parlato di quicksort perchè questa discussione si riferisce esclusivamente all'algoritmo mergesort...

Senza menzionare quicksort, potevi dire che c'è di meglio.

ma la notazione O-grande è utilizzata per descrivere il comportamento asintotico della funzione (in pratica se dico O(n log n) non significa che ho esattamente in media n log n swap)

Possibilmente, evita di confonderti e ascoltami:
Mergesort prende le operazioni O(nlogn) n di elementi nel caso peggiore.
L'ordinamento n degli elementi a due a due distinti provenienti da un campo sconosciuto da un elemento (confrontando) richiede Ω(nlogn)
Ecco perchè Mergesort è asintoticamente peggior caso (ottimale) per l'ordinamento di numeri distinti a coppie la cui gamma è sconosciuta (o grande), tra tutti gli algoritmi di ordinamento a base di confronto.
O(log N) significa che il tempo sale linearmente mentre la n sale in modo esponenziale.

So che stai parlando esclusivamente del mergesort, ma prendi quello che ti sto dicendo come nota ... ;)

 

[ptm]

Senza menzionare quicksort, potevi dire che c'è di meglio.


Possibilmente, evita di confonderti e ascoltami:
Mergesort prende le operazioni O(nlogn) n di elementi nel caso peggiore.
L'ordinamento n degli elementi a due a due distinti provenienti da un campo sconosciuto da un elemento (confrontando) richiede Ω(nlogn)
Ecco perchè Mergesort è asintoticamente peggior caso (ottimale) per l'ordinamento di numeri distinti a coppie la cui gamma è sconosciuta (o grande), tra tutti gli algoritmi di ordinamento a base di confronto.
O(log N) significa che il tempo sale linearmente mentre la n sale in modo esponenziale.

So che stai parlando esclusivamente del mergesort, ma prendi quello che ti sto dicendo come nota ... ;)

Ti avevo solo spiegato cosa significava brevemente la notazione O-grande visto che la tua conoscenza dell'argomento sembrava limitata esclusivamente ad una traduzione (fatta male) di una risposta su stack overflow (

Perfavore, Entra oppure Registrati per vedere i Link!

).

Questa risposta è presa da qui (

Perfavore, Entra oppure Registrati per vedere i Link!

)

O(log N) basically means time goes up linearly while the n goes up exponentially

questa

Mergesort prende le operazioni O(nlogn) n di elementi nel caso peggiore.
L'ordinamento n degli elementi a due a due distinti provenienti da un campo sconosciuto da un elemento (confrontando) richiede Ω(nlogn)
Ecco perchè Mergesort è asintoticamente peggior caso (ottimale) per l'ordinamento di numeri distinti a coppie la cui gamma è sconosciuta (o grande), tra tutti gli algoritmi di ordinamento a base di confronto.

Non è una motivazione e credo tu l'abbia tratta da qualche altra parte (non definisci cosa è gamma e non si sa bene cosa parametrizza).

Comunque cerco di essere chiaro visto che il discorso sta andando a viole... Merge sort e quick sort asintoticamente nel caso medio hanno la stessa complessità computazionale; quick sort nel caso peggiore ha una complessità computazionale peggiore pari ad O(n[SUP]2[/SUP]), ma questa può essere facilmente "mitigata" ricorrendo ad altre tecniche.
Quindi facendo semplicemente un'analisi asintotica della complessità degli algoritmi non è possibile dire che quick sort è meglio di merge sort; la scelta di implementare quick sort in gran parte delle librerie standard dei linguaggi è data dal motivo che quick sort genera meno overhead di merge sort (per motivi architetturali, non per motivi di complessità)

In questo post non voglio offendere nessuno, ma generalmente mi danno molto fastidio le risposte con tono saccente e imprecise. Non sto dicendo che non vanno usate altre fonti per argomentare le proprie affermazioni, ma secondo me prima di tutto queste vanno capite.

 

[Hew0x]

Mi dispiace dirtelo, ma è sempre stato detto quello che ho appena affermato:

Perfavore, Entra oppure Registrati per vedere i Link!

queste cose vanno a memoria (sono delle norme di cui ognuno dovrebbe aver studiato già a memoria):
O(log n) basically means time goes up linearly while the n goes up exponentially. (leggi il sito) ;)
Ma le hai studiate, o no?
Per il resto, mi dispiace ma non sono d'accordo con te

- - - Aggiornato - - -
@ptm ho fatto un esempio proprio per te :

questo mostra l'ordine in cui ogni funzione è chiamata

 

[ptm]

Mi dispiace dirtelo, ma è sempre stato detto quello che ho appena affermato:

Perfavore, Entra oppure Registrati per vedere i Link!

queste cose vanno a memoria (sono delle norme di cui ognuno dovrebbe aver studiato già a memoria):
O(log n) basically means time goes up linearly while the n goes up exponentially. (leggi il sito) ;)
Ma le hai studiate, o no?
Per il resto, mi dispiace ma non sono d'accordo con te

- - - Aggiornato - - -
@ptm ho fatto un esempio proprio per te :

questo mostra l'ordine in cui ogni funzione è chiamata

La frase

O(log n) basically means time goes up linearly while the n goes up exponentially.

non ho detto che era sbagliata; semplicemente non ha correlazione con l'argomento che sto trattando. E' come dire 1+1=2; è vero, ma non c'entra nulla con il discorso.
La complessità del merge sort è O(n log n) che è ben diverso da O(log n). Comunque si, sono cose che ho studiato e non importa se non sei d'accordo. Ti cito una fonte sicuramente più autorevole di me:

Q. How much memory does mergesort require?
A. Too much!

quicksort faster than mergesort in practice because of lower cost of other high-frequency operations.

In breve mergesort è meno efficiente per via del maggiore costo delle sue operazioni (accessi a memoria più frequenti; gli accessi a memoria costano di più) - Fonte ( Princeton University :

Perfavore, Entra oppure Registrati per vedere i Link!

)

ps: l'esempio che hai fatto è uguale all'animazione presente al primo post, solo impaginata in modo diverso. Non ho capito dove vuoi andare a parare.

 

[Hew0x]

Quicksort ha una prestazione peggiore solo quando è ordinato in senso inverso, ha una prestazione migliore solo quando l'input è ordinato

Comunque si, sono cose che ho studiato

E' molto strano, sono delle norme che si dovrebbero studiare a memoria ... Si presume quindi tu non abbia studiato questa citazione fondamentale, e dubitando di me, sei andato a cercare quella frase ( :facepalm: ) che è ovunque:


- - - Aggiornato - - -
@ptm tra l'altro ho letto i due siti, vedo solo quella monotona citazione:
O(log N) basically time goes up linearly while the n goes up exponentially ed è l'equivalente in italiano a quello che dissi prima (che dovresti già sapere a memoria)

 

[ptm]

Anche questo

Si dice che quicksort è molto meglio di mergesort ... Quicksort ha un O(n^2) caso peggiore di runtime e O(nlogn) ha un medio caso di runtime.
E' superiore a merge sort in molti scenari perchè molti fattori influenzano un runtime dell'algoritmo, e ovviamente merge sort perde.
Quicksort richiede poco spazio e presenta una buona frazione di cache, e questo lo rende più veloce di merge sort in molti casi.
Parlando di altre cose, come località di riferimento anche azionano un ruolo importante sull'hardware corrente.
Specificamente, il runtime citata di algoritmi di ordinamento si riferisce al numero di confronti o il numero di swap necessari per eseguire da ordinare i dati. Si, questa è una buona misura della prestazione, perché è indipendente dalla progettazione hardware sottostante.

cha hai spudoratamente copiato da qui (

Perfavore, Entra oppure Registrati per vedere i Link!

) l'hai imparato a memoria?
Semplicemente ti stai arrampicando sugli specchi su concetti che non conosci e che non si imparano a memoria. Non hai risposto ai forti dubbi che ho sollevato sugli strafalcioni che hai scritto fino ad ora.
Ripeto che non voglio offendere nessuno, ma allo stesso modo voglio che tu la smetta di interagire con questi toni. Non sono onnisciente, ma cerco di scrivere guide solo su cose che conosco bene.
Se continuerai oltre qualche altro moderatore di sezione interverrà.

 

[Hew0x]

Anche questo

cha hai spudoratamente copiato da qui (

Perfavore, Entra oppure Registrati per vedere i Link!

) l'hai imparato a memoria?
Semplicemente ti stai arrampicando sugli specchi su concetti che non conosci e che non si imparano a memoria. Non hai risposto ai forti dubbi che ho sollevato sugli strafalcioni che hai scritto fino ad ora.
Ripeto che non voglio offendere nessuno, ma allo stesso modo voglio che tu la smetta di interagire con questi toni. Non sono onnisciente, ma cerco di scrivere guide solo su cose che conosco bene.
Se continuerai oltre qualche altro moderatore di sezione interverrà.

O(log N) time goes up linearly while the n goes up exponentially (ti ho già detto che quest'ultima è una norma che va studiata a memoria, NON è una opinione personale, se no non era in qualunque sito di cui ne parla), poi tutto va imparato concettualmente... non mi fraintendere la prossima volta ;)

se pensi che io non sappia queste cose, tranquillo: te le sai, io no. Non voglio farti perdere l'onore.
poi citami il tutto ;)
Vai con le tue convinzioni, e ricorda: sii meno saccente e più generoso la prossima volta, evita di essere arrogante, ma soprattutto non conosci il prossimo

 

[ptm]

O(log N) time goes up linearly while the n goes up exponentially (ti ho già detto che quest'ultima è una norma che va studiata a memoria, NON è una opinione personale, se no non era in qualunque sito di cui ne parla), poi tutto va imparato concettualmente... non mi fraintendere la prossima volta ;)

se pensi che io non sappia queste cose, tranquillo: te le sai, io no. Non voglio farti perdere l'onore.
poi citami il tutto ;)
Vai con le tue convinzioni, e ricorda: sii meno saccente e più generoso la prossima volta, evita di essere arrogante, ma soprattutto non conosci il prossimo

Ripeto che non è una norma e che non va studiata a memoria... basta sapere cosa è un logaritmo.
Tranquillo, non sono queste cose che mi fanno perdere ""onore""... Riguardo all'ultima frase non meriti nemmeno commento. Ti dico solo che non ho iniziato io a mandare frecciatine e che ho cercato di risponderti nel modo più garbato possibile; se poi non accetti le mie risposte non so cosa dirti. Saluti :bye:

 

[Hew0x]

Ripeto che non è una norma e che non va studiata a memoria... basta sapere cosa è un logaritmo.
Tranquillo, non sono queste cose che mi fanno perdere ""onore""... Riguardo all'ultima frase non meriti nemmeno commento. Ti dico solo che non ho iniziato io a mandare frecciatine e che ho cercato di risponderti nel modo più garbato possibile; se poi non accetti le mie risposte non so cosa dirti. Saluti :bye:

E' due volte o tre che ti dico citami tutto, perchè sei una :censurato: : da quei due siti che mi hai linkato leggo solo O(log N) basically means time goes up linearly while the n goes up exponentially. o meglio frase detta e ridetta (SI, E' UNA NORMA, E VA STUDIATA A MEMORIA) e non:
Mergesort prende le operazioni O(nlogn) n di elementi nel caso peggiore.
L'ordinamento n degli elementi a due a due distinti provenienti da un campo sconosciuto da un elemento (confrontando) richiede Ω(nlogn)
Ecco perchè Mergesort è asintoticamente peggior caso (ottimale) per l'ordinamento di numeri distinti a coppie la cui gamma è sconosciuta (o grande), tra tutti gli algoritmi di ordinamento a base di confronto.
Siccome sei :censurato:, ti dico cos'è una norma (perchè ho visto che non lo sai):
3) Cos’è una norma tecnica?
E’ un documento prodotto mediante consenso e approvato da un organismo riconosciuto, che
fornisce, per usi comuni e ripetuti, regole, linee guida o caratteristiche, relative a determinate
attività o ai loro risultati, al fine di ottenere il migliore ordine in un determinato contesto
(Nota: Una norma dovrebbe basarsi su comprovati risultati scientifici, tecnologici e
sperimentali, e mirare alla promozione dei migliori benefici per la comunità).
Perciò si: non so in che facoltà vai ma esperienza di mio fratello (ingegneria informatica), va studiata a memoria questa norma ;)

 

[TBH]

Quicksort ha una prestazione peggiore solo quando è ordinato in senso inverso, ha una prestazione migliore solo quando l'input è ordinato

E' molto strano, sono delle norme che si dovrebbero studiare a memoria ... Si presume quindi tu non abbia studiato questa citazione fondamentale, e dubitando di me, sei andato a cercare quella frase ( :facepalm: ) che è ovunque:

In realtà non c'è assolutamente nulla da imparare a memoria , dato che ragionando e/o dimostrando matematicamente uno dei due algoritmi si arriva a conclusioni univoche. Senza dover sapere nulla a memoria.
Tra l'altro l'argomento è Il Merge Sort , non il quick sort :soso:

 

[Hew0x]

In realtà non c'è assolutamente nulla da imparare a memoria , dato che ragionando e/o dimostrando matematicamente uno dei due algoritmi si arriva a conclusioni univoche. Senza dover sapere nulla a memoria.
Tra l'altro l'argomento è Il Merge Sort , non il quick sort :soso:

ovvio che è tutta logica, non si dovrebbe studiare a memoria ... ma alcune norme si, poi importa il tutto concettualmente:
ma sono esperienze di mio fratello (te ne avevo già parlato che lui è iscritto alla facoltà di ingegneria informatica, ma questo non ti importa): dipende da come ti fa studiare il tuo professore ... ma poi io vedo solo O(log N) time goes up linearly while the n goes up exponentially similmente citata (apposta , probabilmente per esperienze) , non tutto il resto:

Mergesort prende le operazioni O(nlogn) n di elementi nel caso peggiore.
L'ordinamento n degli elementi a due a due distinti provenienti da un campo sconosciuto da un elemento (confrontando) richiede Ω(nlogn)
Ecco perchè Mergesort è asintoticamente peggior caso (ottimale) per l'ordinamento di numeri distinti a coppie la cui gamma è sconosciuta (o grande), tra tutti gli algoritmi di ordinamento a base di confronto.

perciò caro ptm, pensaci due volte prima di dire fesserie ... è comunque una norma: qualcosa di ripetuto e ripetuto come già ti ho fatto vedere prima (cosa è una norma)

 

[Valerio]

E' due volte o tre che ti dico citami tutto, perchè sei una :censurato: : da quei due siti che mi hai linkato leggo solo O(log N) basically means time goes up linearly while the n goes up exponentially. o meglio frase detta e ridetta (SI, E' UNA NORMA, E VA STUDIATA A MEMORIA) e non:
Mergesort prende le operazioni O(nlogn) n di elementi nel caso peggiore.
L'ordinamento n degli elementi a due a due distinti provenienti da un campo sconosciuto da un elemento (confrontando) richiede Ω(nlogn)
Ecco perchè Mergesort è asintoticamente peggior caso (ottimale) per l'ordinamento di numeri distinti a coppie la cui gamma è sconosciuta (o grande), tra tutti gli algoritmi di ordinamento a base di confronto.
Siccome sei :censurato:, ti dico cos'è una norma (perchè ho visto che non lo sai):
3) Cos’è una norma tecnica?
E’ un documento prodotto mediante consenso e approvato da un organismo riconosciuto, che
fornisce, per usi comuni e ripetuti, regole, linee guida o caratteristiche, relative a determinate
attività o ai loro risultati, al fine di ottenere il migliore ordine in un determinato contesto
(Nota: Una norma dovrebbe basarsi su comprovati risultati scientifici, tecnologici e
sperimentali, e mirare alla promozione dei migliori benefici per la comunità).
Perciò si: non so in che facoltà vai ma esperienza di mio fratello (ingegneria informatica), va studiata a memoria questa norma ;)

Ei, devi cercare di darti una calmata! Va bene esprimere i propri pareri e discutere nei thread dato che siamo in un forum, ma non puoi permetterti di offendere le persone utilizzando certi toni e certi gerghi. Se il tuo scopo è solo quello di alimentare del flame, ti invito a non scrivere più, GRAZIE.

INFRAZIONO e CENSURO.

 

[TBH]

@Hew0x ptm non ha detto nulla di sbagliato, tu hai dato una definizione dove citi gamma ( ma che diavolo rappresenta? )
2°
Caso medio temporalmente del merge e quick sort (quest'ultimo presenta un caso peggiore temporalmente a differenza del merge , ma ptm già lo ha scritto quindi... ) è uguale , ed è : O(n log n) e tu hai citato O(log n) dando una definizione corretta , ma non centra nulla con l'argomento.