Guida al Merge Sort in Python

L’ordinamento dei dati è una delle operazioni più comuni che i praticanti dei dati svolgono nel loro lavoro quotidiano. Molte volte abbiamo bisogno di visualizzare i dati in un certo ordine per estrarre informazioni significative. Fortunatamente, al giorno d’oggi non dobbiamo fare questo compito manualmente. I computer possono fare la magia per noi con prestazioni imbattibili.

Ci sono diverse strategie per ordinare i dati. In questo tutorial, analizzeremo una delle tecniche di ordinamento più efficaci. L’algoritmo “merge sort” utilizza una strategia divide-et-impera per ordinare un array non ordinato suddividendolo in array più piccoli, che vengono successivamente uniti nell’ordine corretto.

Nelle prossime sezioni, discuteremo tutti i dettagli dell’algoritmo di merge sort, come appare in Python, e alcuni consigli pratici per una implementazione senza intoppi.

Cos’è il Merge Sort?

Ci sono molti algoritmi di ordinamento là fuori, ma è difficile trovarne uno che funzioni meglio del merge sort. Non sorprendentemente, questo algoritmo è utilizzato in tutti i tipi di applicazioni del mondo reale, come l’ordinamento di grandi database o l’organizzazione dei file su un computer tradizionale.

L’algoritmo si basa sul paradigma divide-et-impera, che può essere suddiviso in tre parti:

• Dividi: questo processo suddivide il problema in sotto-problemi più piccoli.
• Conquista: i sotto-problemi sono risolti in modo ricorsivo.
• Combina: le soluzioni dei sotto-problemi vengono combinate per ottenere la soluzione finale.

Strategia divide-et-impera

Vediamo come funziona il merge sort. Supponiamo di voler ordinare i seguenti numeri applicando l’algoritmo di merge sort. L’algoritmo divide i dati in modo ricorsivo in due parti e continua a dividere fino a quando ogni lista ha un solo elemento. Successivamente, li combiniamo ordinandoli in un’altra lista.

Problema del Merge Sort. Fonte: DataCamp

Complessità Temporale e Spaziale del Merge Sort

È impossibile sapere in anticipo quale algoritmo di ordinamento funzioni meglio per un determinato problema. Diverse variabili devono essere considerate oltre all’algoritmo, incluso il linguaggio di programmazione utilizzato per scrivere il codice, l’hardware in cui vengono eseguiti e le particolarità dei dati da ordinare. 

Anche se non possiamo prevedere il tempo di esecuzione esatto di un algoritmo di ordinamento, possiamo comunque confrontare le prestazioni di vari algoritmi di ordinamento analizzando la complessità temporale e spaziale.

Complessità temporale di merge sort

Come spiegato in una guida separata su Notazione Big O e Complessità Temporale, l’obiettivo dell’analisi della complessità temporale non è prevedere il tempo di esecuzione esatto di un algoritmo, ma piuttosto valutare quanto è efficiente un algoritmo analizzando come il suo tempo di esecuzione cambia con l’aumentare della quantità di dati in ingresso.

L’analisi della complessità temporale è scritta in notazione Big O, una notazione matematica che descrive il tasso al quale una funzione cresce o decresce. Il merge sort ha una complessità temporale log-lineare o linearitmica, indicata come O(N log(N)), dove N è il numero di elementi nella lista. La lettera ‘O’ rappresenta l’ ‘ordine’ di crescita.

Nell’analisi della complessità temporale, la complessità linearitmica si comporta approssimativamente in modo simile alla complessità lineare, il che significa che la sua esecuzione sarà direttamente proporzionale alla quantità di dati. Pertanto, se la quantità di dati viene raddoppiata, anche il tempo necessario all’algoritmo per elaborare i dati dovrebbe raddoppiare, cioè il numero di divisioni e fusioni raddoppierà.

Poiché la complessità temporale del merge sort si comporta in modo lineare, la sua complessità rimane la stessa per i casi migliori, medi e peggiori. Ciò significa che, indipendentemente dall’ordine di ingresso, l’algoritmo richiederà sempre lo stesso numero di passi per completarsi.

Complesso di spazio del merge sort

Infine, oltre al tempo necessario per completare il compito, un altro aspetto importante nell’analizzare la complessità di un algoritmo è stimare quanta memoria l’algoritmo richiederà per completare man mano che il problema diventa più grande.

Questo è coperto dai concetti di complessità dello spazio e spazio ausiliario. Quest’ultimo si riferisce allo spazio extra o temporaneo utilizzato da un algoritmo, mentre il primo si riferisce allo spazio totale occupato dall’algoritmo rispetto alla dimensione dell’input. In altre parole, la complessità dello spazio include sia lo spazio ausiliario che lo spazio utilizzato dall’input.

Il merge sort ha una complessità dello spazio di O(N). Questo perché utilizza un array ausiliario di dimensione N per unire le metà ordinate dell’array di input. L’array ausiliario viene utilizzato per memorizzare il risultato unito e l’array di input viene sovrascritto con il risultato ordinato.

Implementazione del Merge Sort in Python

Implementiamo l’algoritmo di merge sort in Python. Ci sono diversi modi per codificare l’algoritmo; tuttavia, ci atteniamo a quello basato sulla ricorsione, che è probabilmente il più semplice da capire e richiede meno righe di codice rispetto ad altre alternative basate sull’iterazione.

Comprensione della ricorsione in merge sort

Se sei nuovo all’argomento, nella programmazione la ricorsione avviene quando una funzione si chiama da sola. Puoi consultare il nostro Tutorial sulla Comprensione delle Funzioni Ricorsive in Python per imparare tutto su queste potenti funzioni.

Per implementare il merge sort, prima definiamo il caso base: se la lista ha solo un elemento, è già ordinata, quindi restituiamo immediatamente. Altrimenti, dividiamo la lista in due metà, left_half e right_half, e chiamiamo merge_sort() ricorsivamente su ciascuna di esse. Questo processo continua finché tutte le sottoliste contengono un singolo elemento.

Una volta che abbiamo queste sottoliste ordinate, iniziamo il processo di fusione. Per fare ciò, inizializziamo tre variabili di indice: i per tracciare la posizione in left_half, j per right_half, e k per la lista fusa finale. Quindi confrontiamo gli elementi da entrambe le metà. Se l’elemento corrente in left_half è più piccolo, lo mettiamo in my_list[k] e spostiamo i avanti. Altrimenti, prendiamo l’elemento da right_half, lo mettiamo in my_list[k] e incrementiamo j. Dopo ogni confronto, spostiamo k avanti alla posizione successiva nella lista finale.

Questo processo continua finché abbiamo confrontato tutti gli elementi in una delle metà. Se rimangono elementi in left_half o right_half, li aggiungiamo direttamente alla lista finale, garantendo che nessun dato venga lasciato indietro. Poiché il merge sort opera in modo ricorsivo, questo processo di fusione viene eseguito ad ogni livello di ricorsione fino a quando l’intera lista è ordinata.

Implementazione in Python

Di seguito, puoi trovare il codice utilizzando l’elenco non ordinato del diagramma precedente come esempio:

def merge_sort(my_list):
    if len(my_list) > 1: 
        mid = len(my_list)//2
        left_half = my_list[:mid]
        right_half = my_list[mid:]
       
        merge_sort(left_half)
        merge_sort(right_half)

        i = j = k = 0
 
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                my_list[k] = left_half[i]                
                i += 1
            else:
                my_list[k] = right_half[j]
                j += 1
            k += 1
     
        while i < len(left_half):
            my_list[k] = left_half[i]
            i += 1
            k += 1
 
        while j < len(right_half):
            my_list[k] = right_half[j]
            j += 1
            k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)
>>> [1, 4, 20, 22, 30, 35, 40, 50, 90]

Merge Sort vs Altri Algoritmi di Ordinamento

Il merge sort è un algoritmo di ordinamento piuttosto veloce, particolarmente adatto per grandi database, ed è spesso usato come riferimento per altri algoritmi. Tuttavia, per liste più brevi, le sue prestazioni tendono ad essere inferiori rispetto ad altri algoritmi di ordinamento.

Nella tabella seguente, puoi trovare un confronto del merge sort con altri popolari algoritmi di ordinamento.

Applicazioni pratiche di Merge Sort

Merge sort ha prestazioni elevate nel ordinare grandi liste, ma la sua efficienza diminuisce quando si lavora con liste più piccole. Allo stesso modo, tende ad essere meno efficiente in scenari in cui esiste già un certo grado di ordine nelle liste di input, poiché merge sort eseguirà gli stessi passaggi indipendentemente dall’ordine della lista.

Un ottimo caso d’uso in cui merge sort risulta particolarmente utile sono le liste collegate. Una lista collegata è una struttura dati che comprende un collegamento di nodi collegati linearmente tra loro. Ogni nodo contiene i dati e il collegamento per connetterlo al nodo successivo.

Il merge sort è preferito per le liste collegate perché richiede solo un accesso sequenziale ai dati, il che si allinea bene con la natura delle liste collegate. Inoltre, il merge sort è un algoritmo di ordinamento stabile (ovvero, preserva l’ordine relativo degli elementi uguali nell’output ordinato), che è una considerazione molto importante nel mantenere l’ordine delle liste collegate.

Errori Comuni e Risoluzione dei Problemi

L’algoritmo merge sort è piuttosto diretto e il margine di miglioramento nel codice è limitato. Tuttavia, è possibile aumentare la complessità della strategia di ordinamento tenendo conto delle dimensioni dei dati di input.

Abbiamo già stabilito che merge sort funziona meglio con set di dati più grandi. Per set di dati più piccoli, altri algoritmi di ordinamento con complessità temporale O(N^2), come insertion sort, potrebbero funzionare meglio. In questo caso, dovresti semplicemente creare una soglia di dimensione al di sotto della quale opteresti per l’algoritmo insertion sort anziché merge sort.

Altre idee interessanti da esplorare potrebbero riguardare la parallelizzazione. I passaggi del merge sort possono essere facilmente parallelizzati con la giusta potenza di calcolo, riducendo così il tempo necessario per completare l’operazione. Leggi la nostra guida CPU vs GPU per saperne di più sulla computazione parallela. 

Conclusione

Il merge sort è uno degli algoritmi di ordinamento più efficaci e popolari, ma c’è ancora molto da imparare nel meraviglioso e sempre in espansione universo degli algoritmi. Se sei interessato alle tecniche degli algoritmi, al loro funzionamento e alla loro complessità, virtù e svantaggi associati, queste risorse di DataCamp possono aiutarti a continuare il tuo apprendimento:

• Corso di Introduzione alle Strutture Dati e agli Algoritmi
• Percorso di Abilità di Programmazione Python
• Percorso di Fondamenti dei Dati in Python
• Corso di Python Intermedio
• Percorso di Carriera di Analista Dati in Python
• Notazione Big O e Complessità Temporale