|
|
Analizziamo l’ algoritmo Mergesort, che è un algoritmo di ordinamento basato sulla tecnica di“Divide et Impera” per ordinare un vettore A[.] di n interi. L’ idea di base è quella di suddividere il vettore in 2 parti, ordinarle e poi “fonderle” insieme. In linguaggio C:
Grazie alle chiamate ricorsive viene partizionato il vettore nel seguente modo:
Per fondere le due metà viene chiamata la funzione “merge”, che fa uso di un vettore di appoggio B esterno:
Quando la funzione rientra dalle due chiamate ricorsive, il vettore A[.] risulta composto di due sequenze ordinate, quindi la combinazione dei risultati ottenuta on “merge” consiste nel “fondere” due sequenze ordinate. La fusione dei dati che otterremo può essere schematizzata in questo modo:
Poiché la funzione MERGE ha complessità O(n), allora T(n) di MERGESORT è O(n log n), infatti assumendo c e d due costanti positive, si ottiene:
e applicando il teorema di ricorrenze lineare bilanciate avremo:
Comunque algoritmi di ordinamento basati su questa tecnica risultano vantaggiosi qualora gli elementi da ordinare risiedano in memoria secondaria (per esempio su disco), che è capiente ma più lenta. Quindi conviene i dati in blocchi sequenziali, proprio come avviene nella funzione MERGE.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.