Mergesort e Quicksort: Due Approcci Dominanti per l’Ordinamento Efficiente

Mergesort e Quicksort header

L’ordinamento di dati è una delle operazioni fondamentali nell’ambito dell’informatica, e la scelta di un algoritmo di ordinamento appropriato può influenzare significativamente le prestazioni di un’applicazione. Due degli algoritmi più noti e ampiamente utilizzati sono Mergesort e Quicksort. Questi due approcci, entrambi basati sul principio “divide et impera”, sono in grado di ordinare sequenze di dati in modo efficiente, ma adottano strategie diverse per raggiungere questo obiettivo.

  • Python
    • Algoritmi
      • Alberi
        e Grafi
      • Strutture dati
        Avanzate
      • Numerici
      • Ordinamento
        e Ricerca
      • Ricorsione
        Backtracking
Mergesort e Quicksort

Mergesort e Quicksort

Mergesort e Quicksort sono algoritmi di ordinamento efficienti e molto utilizzati. Ogni algoritmo ha le sue caratteristiche e punti di forza, ma entrambi utilizzano l’approccio “divide et impera” per ordinare una sequenza di elementi.

Mergesort, ideato da John von Neumann e sviluppato ulteriormente da John McCarthy, è noto per la sua stabilità e la complessità temporale garantita. Questo algoritmo opera suddividendo la sequenza in due parti, ordinando separatamente ciascuna parte, e infine combinando le parti in una sequenza ordinata. La stabilità di Mergesort è particolarmente utile quando è necessario mantenere l’ordine relativo degli elementi con chiavi uguali. L’efficienza di Mergesort è evidenziata dalla sua complessità temporale O(n log n), rendendolo una scelta affidabile per sequenze di dati di diverse dimensioni.

Quicksort, Inventato da Tony Hoare, si distingue per la sua velocità e semplicità. Questo algoritmo opera suddividendo la sequenza attraverso un elemento pivot, posizionando gli elementi minori a sinistra e quelli maggiori a destra. Successivamente, le due parti risultanti sono ordinate separatamente, senza la necessità di una fase di combinazione. La complessità temporale media di Quicksort è anch’essa O(n log n), rendendolo altamente efficiente nella pratica. Tuttavia, è importante notare che il suo peggior caso può comportare una complessità temporale quadratica, se la scelta del pivot non è gestita attentamente.

Mergesort

Mergesort è stato inventato da John von Neumann nel 1945, anche se la versione moderna è stata sviluppata da John McCarthy nel 1956. Mergesort è noto per la sua stabilità e per la sua complessità temporale garantita.

L’algoritmo Mergesort funziona nel seguente modo:

  1. Divide: La sequenza di elementi è divisa in due parti uguali.
  2. Conquista: Ciascuna parte è ordinata separatamente utilizzando ricorsivamente l’algoritmo Mergesort.
  3. Combina: Le due parti ordinate vengono fuse (merge) per creare una sequenza ordinata.

Questo processo di dividere, ordinare e combinare continua ricorsivamente fino a quando la sequenza è completamente ordinata. Mergesort è noto per la sua stabilità, il che significa che mantiene l’ordine relativo degli elementi con chiave uguale.

La complessità temporale di Mergesort è O(n log n), dove “n” è la dimensione della sequenza. Questo rende Mergesort un algoritmo efficiente, anche se richiede spazio aggiuntivo per la fusione delle sequenze.

def mergesort(arr):
    if len(arr) <= 1:
        return arr

    middle = len(arr) // 2
    left_half = mergesort(arr[:middle])
    right_half = mergesort(arr[middle:])

    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0

    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    result.extend(left[i:])
    result.extend(right[j:])
    return result

# Esempio di utilizzo:
lista_non_ordinata = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
lista_ordinata_merge = mergesort(lista_non_ordinata)
print("Mergesort:", lista_ordinata_merge)

Eseguendo il codice otterrai il risultato seguente:

Mergesort: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Quicksort

Storia e Origini:
Quicksort è stato inventato da Tony Hoare nel 1960 ed è noto per la sua velocità e semplicità. È uno degli algoritmi di ordinamento più utilizzati e viene spesso utilizzato nelle librerie standard di molti linguaggi di programmazione.

L’algoritmo Quicksort funziona nel seguente modo:

  1. Partiziona: Un elemento, noto come “pivot”, viene scelto dalla sequenza. Gli elementi minori del pivot vengono posti a sinistra, mentre quelli maggiori vengono posti a destra.
  2. Conquista: Le due parti risultanti (a sinistra e a destra del pivot) vengono ordinatamente separate, usando ricorsivamente l’algoritmo Quicksort.
  3. Combina: Poiché ogni partizione è già ordinata, non è necessaria alcuna fase di combinazione.

Questo processo di partizionamento e ordinamento ricorsivo continua fino a quando l’intera sequenza è ordinata. Quicksort è noto per la sua velocità, soprattutto in media, anche se il suo peggior caso può essere O(n^2) in situazioni specifiche.

La complessità temporale media di Quicksort è O(n log n), rendendolo molto efficiente nella pratica. Tuttavia, il suo peggior caso si verifica quando il pivot viene scelto in modo sfavorevole, portando a una complessità temporale quadratica. Per mitigare questo problema, le implementazioni moderne di Quicksort utilizzano strategie per la scelta intelligente del pivot.

def quicksort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        lesser = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        return quicksort(lesser) + [pivot] + quicksort(greater)

# Esempio di utilizzo:
lista_non_ordinata = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
lista_ordinata_quick = quicksort(lista_non_ordinata)
print("Quicksort:", lista_ordinata_quick)

Eseguendo il codice otterrai il seguente risultato:

Quicksort: [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

Conclusione

In sintesi, Mergesort e Quicksort sono entrambi algoritmi di ordinamento efficienti che utilizzano l’approccio “divide et impera”. Mergesort è noto per la sua stabilità, mentre Quicksort è noto per la sua velocità media. La scelta tra i due dipende spesso dalle specifiche esigenze del problema e dalle caratteristiche dei dati da ordinare.

Lascia un commento