02 - Sorting algorithms: bubble, merge, quick, heap

Devi ordinare una lista e in libreria c'è già una funzione che lo fa, quindi la domanda sensata non è «come si scrive un ordinamento» ma «che cosa fa quella funzione, quando mi tradisce e perché i manuali ne descrivono quattro». Bubble, merge, quick e heap sort rispondono alla stessa richiesta con compromessi diversi: tempo nel caso peggiore, memoria aggiuntiva, comportamento con i duplicati. Per scegliere bene devi vedere i numeri, non memorizzare una tabella di sigle.

Questo è il secondo articolo della serie Algoritmi e Strutture Dati e riprende il metodo del primo: ogni complessità è accompagnata da un conteggio di confronti. Implemento i quattro algoritmi in Python 3.14 (python3 -I, sola libreria standard), li verifico contro sorted e contro tutte le permutazioni fino a sei elementi, e costruisco i casi peggiori invece di nominarli. Le uscite sono quelle ottenute eseguendo i listati due volte con risultato identico.

Che cosa si misura e come si controlla la correttezza

Un ordinamento per confronti ha un solo costo di riferimento: il numero di volte in cui confronta due chiavi. Ogni listato conta quel numero. Gli elementi sono coppie (chiave, etichetta) e si confronta solo la chiave: così, con chiavi ripetute, l'etichetta rivela se l'ordine originale dei duplicati è stato conservato, cioè se l'algoritmo è stabile. La documentazione di Python garantisce che sorted lo sia, e per questo la uso come riferimento anche per la stabilità.

La correttezza non si dichiara, si prova nel solo modo che scala: tutte le permutazioni da 0 a 6 elementi (sono 874 ingressi in totale, e coprono ogni ordine relativo possibile per liste piccole) e poi 3.000 liste casuali con molti duplicati e seme fisso. Una proprietà che regge su tutti gli ingressi piccoli non è una dimostrazione, ma cattura la quasi totalità degli errori di indice e di partizione che si commettono scrivendo questi algoritmi a mano.

Bubble sort: il caso peggiore è il caso inverso

Bubble sort scorre la lista scambiando ogni coppia adiacente fuori ordine; a ogni passaggio il massimo «sale» in fondo. La versione con uscita anticipata si ferma al primo passaggio senza scambi. Il listato la verifica e confronta il conteggio sul caso già ordinato e su quello inverso. Il confronto indipendente è il numero di inversioni, le coppie (i, j) con i < j e chiave maggiore, calcolato per forza bruta.

# Bubble sort con uscita anticipata. Gli elementi sono coppie (chiave, etichetta): si confronta solo la chiave.
import itertools, random

def bubble_sort(a):
    a, comparisons, swaps = a[:], 0, 0
    for end in range(len(a) - 1, 0, -1):
        swapped = False
        for i in range(end):
            comparisons += 1
            if a[i][0] > a[i + 1][0]:
                a[i], a[i + 1] = a[i + 1], a[i]
                swaps += 1
                swapped = True
        if not swapped:                      # un passaggio senza scambi: gia' ordinato
            break
    return a, comparisons, swaps

def inversions(keys):                        # riferimento indipendente, forza bruta
    return sum(1 for i in range(len(keys)) for j in range(i + 1, len(keys)) if keys[i] > keys[j])

# correttezza: TUTTE le permutazioni fino a n = 6, poi 3000 casi casuali con duplicati (seme fisso)
for n in range(0, 7):
    for p in itertools.permutations(range(n)):
        out, _, sw = bubble_sort([(k, k) for k in p])
        assert [k for k, _ in out] == sorted(p) and sw == inversions(p)
rng = random.Random(1)
for _ in range(3000):
    a = [(rng.randrange(8), t) for t in range(rng.randrange(0, 40))]
    out, _, sw = bubble_sort(a)
    assert out == sorted(a, key=lambda x: x[0])          # sorted() e' stabile: confronto anche delle etichette
    assert sw == inversions([k for k, _ in a])
print("bubble sort: corretto, stabile, scambi == inversioni (permutazioni n<=6 e 3000 casi)")

print(f"{'n':>5} {'ordinato':>9} {'inverso':>9} {'n(n-1)/2':>9} {'scambi inverso':>15}")
for n in (50, 100, 200, 400):
    _, c0, _ = bubble_sort([(k, k) for k in range(n)])
    _, c1, s1 = bubble_sort([(k, k) for k in range(n, 0, -1)])
    print(f"{n:>5} {c0:>9} {c1:>9} {n * (n - 1) // 2:>9} {s1:>15}")

# Output:
# bubble sort: corretto, stabile, scambi == inversioni (permutazioni n<=6 e 3000 casi)
#     n  ordinato   inverso  n(n-1)/2  scambi inverso
#    50        49      1225      1225            1225
#   100        99      4950      4950            4950
#   200       199     19900     19900           19900
#   400       399     79800     79800           79800

Ogni scambio elimina esattamente una inversione, per questo il controllo «scambi == inversioni» passa su tutti gli ingressi: è la proprietà che governa il costo. Sul caso inverso i confronti sono n(n − 1)/2 e gli scambi sono altrettanti (400 elementi: 79.800 e 79.800); sul caso ordinato con l'uscita anticipata i confronti scendono a n − 1. Senza l'uscita anticipata il caso ordinato costerebbe comunque quadratico, ed è il tipico errore di chi lo implementa dal manuale. Bubble sort resta uno strumento didattico: scambia più di quanto serva, e i due algoritmi seguenti lo battono già a poche centinaia di elementi.

Merge sort: dividere, ordinare, fondere

Merge sort divide la lista a metà, ordina le due metà e le fonde con un solo passaggio. La fusione è il punto delicato: confronta le teste delle due metà e prende la minore. Nel listato la condizione src[j][0] < src[i][0] usa il minore stretto, quindi a parità di chiave vince l'elemento di sinistra, ed è questa riga a rendere l'algoritmo stabile. Se la sostituisci con <= il risultato resta ordinato ma l'ordine dei duplicati si inverte, e il confronto con sorted lo segnala.

# Merge sort con buffer ausiliario: conteggio dei confronti, caso peggiore COSTRUITO, limite inferiore
import itertools, math, random

def merge_sort(a):
    comparisons = 0
    def sort(lo, hi, src, buf):              # ordina src[lo:hi] usando buf come appoggio
        nonlocal comparisons
        if hi - lo < 2:
            return
        mid = (lo + hi) // 2
        sort(lo, mid, src, buf)
        sort(mid, hi, src, buf)
        i, j, k = lo, mid, lo
        while i < mid and j < hi:
            comparisons += 1
            if src[j][0] < src[i][0]:        # '<' stretto: a parita' vince la sinistra => stabile
                buf[k] = src[j]; j += 1
            else:
                buf[k] = src[i]; i += 1
            k += 1
        buf[k:hi] = src[i:mid] if i < mid else src[j:hi]
        src[lo:hi] = buf[lo:hi]
    out = a[:]
    sort(0, len(out), out, [None] * len(out))
    return out, comparisons

def worst_input(keys):                       # "de-fonde": sinistra = posizioni pari, destra = dispari
    if len(keys) < 2:
        return keys
    return worst_input(keys[0::2]) + worst_input(keys[1::2])

for n in range(0, 7):
    for p in itertools.permutations(range(n)):
        assert [k for k, _ in merge_sort([(k, k) for k in p])[0]] == sorted(p)
rng = random.Random(2)
for _ in range(3000):
    a = [(rng.randrange(8), t) for t in range(rng.randrange(0, 60))]
    assert merge_sort(a)[0] == sorted(a, key=lambda x: x[0])      # include la stabilita'
print("merge sort: corretto e stabile (permutazioni n<=6 e 3000 casi)")

print(f"{'n':>5} {'casuale (media 20)':>19} {'peggiore costruito':>19} {'n lg n - n + 1':>15} {'ceil(lg n!)':>12}")
for n in (64, 256, 1024, 2048):
    avg = sum(merge_sort([(k, k) for k in rng.sample(range(n), n)])[1] for _ in range(20)) / 20
    worst = merge_sort([(k, k) for k in worst_input(list(range(n)))])[1]
    bound = math.ceil(math.log2(math.factorial(n)))
    print(f"{n:>5} {avg:>19.0f} {worst:>19} {n * int(math.log2(n)) - n + 1:>15} {bound:>12}")

# Output:
# merge sort: corretto e stabile (permutazioni n<=6 e 3000 casi)
#     n  casuale (media 20)  peggiore costruito  n lg n - n + 1  ceil(lg n!)
#    64                 306                 321             321          296
#   256                1725                1793            1793         1684
#  1024                8942                9217            9217         8770
#  2048               19942               20481           20481        19581

Il caso peggiore non si trova per caso: la funzione worst_input lo costruisce «de-fondendo» una lista ordinata, mettendo a sinistra le posizioni pari e a destra le dispari, ricorsivamente, in modo che ogni fusione debba consumare entrambe le metà fino in fondo. I confronti su quell'ingresso coincidono con n lg n − n + 1 per n potenza di due (321, 1.793, 9.217, 20.481 nelle righe della tabella). Il caso casuale è più basso (19.942 per n = 2.048) ma non di molto: per merge sort il caso migliore e il peggiore sono entro un fattore piccolo.

L'ultima colonna è un limite che nessun algoritmo per confronti può battere. Una lista di n chiavi distinte può essere in n! ordini, e ogni confronto ha due esiti, quindi servono almeno ⌈log₂(n!)⌉ confronti nel caso peggiore: 19.581 per n = 2.048. Merge sort ne usa 20.481 al massimo, cioè il 4,6% in più; per questo si dice che è asintoticamente ottimo. Il prezzo è lo spazio: il buffer ausiliario è lungo quanto l'ingresso, quindi O(n) in memoria extra. Quick sort e heap sort, che non hanno un buffer proporzionale all'ingresso, mostrano la differenza di spazio a parità di tempo medio.

Quick sort: il pivot decide tutto

Quick sort sceglie un elemento (il pivot), sposta a sinistra i minori e a destra i maggiori, poi ordina le due parti. Il costo dipende da quanto le due parti sono equilibrate. Il listato usa la partizione di Lomuto con il pivot all'ultimo posto, oppure con un pivot scelto a caso, e al posto della ricorsione usa una pila esplicita: dopo ogni partizione rimanda in pila la parte più grande e prosegue sulla più piccola. Questa regola limita la pila a O(log n) elementi, qualunque sia l'ingresso.

# Quick sort (partizione di Lomuto) con pila esplicita: si rimanda la parte piu' grande, si prosegue sulla piu' piccola
import itertools, random

def quick_sort(a, pivot="last", rng=None):
    a, comparisons, stack, max_stack = a[:], 0, [(0, len(a) - 1)], 1
    while stack:
        lo, hi = stack.pop()
        while lo < hi:
            if pivot == "random":
                r = rng.randint(lo, hi)
                a[r], a[hi] = a[hi], a[r]
            p, store = a[hi][0], lo
            for i in range(lo, hi):
                comparisons += 1
                if a[i][0] < p:
                    a[i], a[store] = a[store], a[i]
                    store += 1
            a[store], a[hi] = a[hi], a[store]
            left, right = (lo, store - 1), (store + 1, hi)
            if left[1] - left[0] < right[1] - right[0]:   # la parte piu' grande va in pila
                stack.append(right); hi = store - 1
            else:
                stack.append(left); lo = store + 1
            max_stack = max(max_stack, len(stack))
    return a, comparisons, max_stack

for n in range(0, 7):
    for p in itertools.permutations(range(n)):
        assert [k for k, _ in quick_sort([(k, k) for k in p])[0]] == sorted(p)
rng = random.Random(3)
for _ in range(3000):
    a = [(rng.randrange(8), t) for t in range(rng.randrange(0, 60))]
    for mode in ("last", "random"):
        assert [k for k, _ in quick_sort(a, mode, rng)[0]] == sorted(k for k, _ in a)
stable = quick_sort([(0, t) for t in range(2)] + [(1, 9)] + [(0, 5)])[0]
print("quick sort: corretto (permutazioni n<=6, 3000 casi x 2 pivot). Ordine delle etichette a parita':",
      [t for k, t in stable if k == 0], "(non e' garantito stabile)")

print(f"{'n':>5} {'ordinato, pivot ultimo':>23} {'n(n-1)/2':>9} {'pila max':>9} | {'ordinato, pivot casuale (media 10)':>34} {'casuale, pivot ultimo':>22} {'2(n+1)Hn-4n':>12}")
for n in (256, 512, 1024, 2048):
    srt = [(k, k) for k in range(n)]
    _, cw, depth = quick_sort(srt)
    cr = sum(quick_sort(srt, "random", rng)[1] for _ in range(10)) / 10
    cavg = sum(quick_sort([(k, k) for k in rng.sample(range(n), n)])[1] for _ in range(10)) / 10
    h = sum(1 / i for i in range(1, n + 1))          # numero armonico H_n
    print(f"{n:>5} {cw:>23} {n * (n - 1) // 2:>9} {depth:>9} | {cr:>34.0f} {cavg:>22.0f} {2 * (n + 1) * h - 4 * n:>12.0f}")

# Output:
# quick sort: corretto (permutazioni n<=6, 3000 casi x 2 pivot). Ordine delle etichette a parita': [5, 0, 1] (non e' garantito stabile)
#     n  ordinato, pivot ultimo  n(n-1)/2  pila max | ordinato, pivot casuale (media 10)  casuale, pivot ultimo  2(n+1)Hn-4n
#   256                   32640     32640         1 |                               2181                   2203         2124
#   512                  130816    130816         1 |                               4693                   5006         4946
#  1024                  523776    523776         1 |                              11514                  11244        11298
#  2048                 2096128   2096128         1 |                              25108                  26125        25420

Sull'ingresso già ordinato con pivot all'ultimo posto ogni partizione isola un solo elemento, e i confronti sono esattamente n(n − 1)/2 (2.096.128 per n = 2.048, identico alla formula). È il caso peggiore reale, e capita con i dati che arrivano già quasi ordinati. Con il pivot casuale lo stesso ingresso costa circa 25.000 confronti, vicino al valore atteso 2(n + 1)Hₙ − 4n della quarta colonna (25.420), dove Hₙ è il numero armonico: il caso peggiore esiste ancora, ma non si può più costruire in anticipo guardando l'ingresso.

Due dettagli dell'uscita vanno letti. La pila massima è 1 anche nel caso quadratico: la regola «prosegui sulla parte più piccola» fa sì che la memoria resti piccola quando il tempo non lo è, e come nel primo articolo tempo e spazio vanno contati separatamente. E le etichette dei duplicati escono nell'ordine 5, 0, 1: quick sort non è stabile, e la riga lo mostra su un esempio costruito (non è un teorema, è una dimostrazione per controesempio).

Heap sort: nessun caso peggiore quadratico e nessuna memoria extra

Heap sort trasforma la lista in un heap massimo, cioè un albero binario memorizzato nella lista in cui ogni nodo è maggiore dei suoi figli, e poi estrae il massimo n − 1 volte portandolo in fondo. La costruzione procede dal basso, partendo dall'ultimo nodo con figli, e per questo costa O(n) e non O(n log n): i nodi vicini alle foglie hanno poco da scendere. Il listato conta separatamente i confronti della costruzione e quelli totali.

# Heap sort: costruzione dal basso (heapify) e poi n-1 estrazioni, con confronti contati separatamente
import itertools, math, random

def heap_sort(a):
    a, comparisons = a[:], 0
    def sift_down(root, end):                # end: indice escluso
        nonlocal comparisons
        while 2 * root + 1 < end:
            child = 2 * root + 1
            if child + 1 < end:
                comparisons += 1
                if a[child][0] < a[child + 1][0]:
                    child += 1               # il figlio maggiore
            comparisons += 1
            if a[root][0] < a[child][0]:
                a[root], a[child] = a[child], a[root]
                root = child
            else:
                return
    n = len(a)
    for root in range(n // 2 - 1, -1, -1):   # costruzione: O(n), non O(n log n)
        sift_down(root, n)
    build = comparisons
    for end in range(n - 1, 0, -1):          # il massimo va in fondo, l'heap si accorcia
        a[0], a[end] = a[end], a[0]
        sift_down(0, end)
    return a, build, comparisons

for n in range(0, 7):
    for p in itertools.permutations(range(n)):
        assert [k for k, _ in heap_sort([(k, k) for k in p])[0]] == sorted(p)
rng = random.Random(4)
for _ in range(3000):
    a = [(rng.randrange(8), t) for t in range(rng.randrange(0, 60))]
    assert [k for k, _ in heap_sort(a)[0]] == sorted(k for k, _ in a)
unst = heap_sort([(0, 0), (0, 1), (0, 2), (0, 3)])[0]
print("heap sort: corretto. Etichette di quattro chiavi uguali, in uscita:", [t for _, t in unst], "(non stabile)")

print(f"{'n':>5} {'costruzione':>12} {'2n':>6} {'totale casuale':>15} {'ordinato':>9} {'inverso':>9} {'2n lg n':>8}")
for n in (64, 256, 1024, 2048):
    _, b, tot = heap_sort([(k, k) for k in rng.sample(range(n), n)])
    _, _, t_sorted = heap_sort([(k, k) for k in range(n)])
    _, _, t_rev = heap_sort([(k, k) for k in range(n, 0, -1)])
    print(f"{n:>5} {b:>12} {2 * n:>6} {tot:>15} {t_sorted:>9} {t_rev:>9} {2 * n * int(math.log2(n)):>8}")

# Output:
# heap sort: corretto. Etichette di quattro chiavi uguali, in uscita: [1, 2, 3, 0] (non stabile)
#     n  costruzione     2n  totale casuale  ordinato   inverso  2n lg n
#    64          104    128             573       593       525      768
#   256          460    512            3317      3452      3106     4096
#  1024         1941   2048           17320     18060     16407    20480
#  2048         3839   4096           38733     40204     36973    45056

La costruzione costa meno di 2n confronti in ogni riga (1.941 contro 2.048 per n = 1.024), il che conferma il limite lineare. Il totale cresce come n log n con una costante vicina a 2 (38.733 per n = 2.048, a fronte di 2n lg n = 45.056), perché ogni passo di discesa fa due confronti, uno fra i figli e uno con il padre. A differenza di quick sort il costo è praticamente identico per ingressi ordinati, inversi e casuali, e non serve memoria oltre alla lista. La contropartita è l'instabilità, visibile nelle quattro chiavi uguali uscite nell'ordine 1, 2, 3, 0, e una scarsa località degli accessi, che qui non misuro.

Gli heap servono anche fuori dall'ordinamento, per estrarre sempre il minimo o il massimo: li riprendi con le code a priorità nell'articolo sulle strutture lineari e con gli alberi nell'articolo sui BST e gli AVL.

Quale scegliere: la tabella delle proprietà

• Bubble sort: Θ(n²) nel caso peggiore, spazio O(1), stabile; n − 1 confronti sul già ordinato solo con l'uscita anticipata.
• Merge sort: n lg n − n + 1 confronti nel caso peggiore (n potenza di due), spazio O(n), stabile.
• Quick sort: n(n − 1)/2 nel caso peggiore, in media circa 2(n + 1)Hₙ − 4n confronti (il termine principale è 1,39 n lg n) con pivot casuale, pila O(log n) con la regola della parte più piccola, non stabile.
• Heap sort: O(n log n) in ogni caso, spazio O(1) aggiuntivo, non stabile, costruzione lineare.

Le righe non si classificano in un ordine unico: dipende da quale proprietà ti serve. Se i duplicati portano informazione (ordinare record per un campo, poi per un altro) ti serve la stabilità, e restano solo merge sort e bubble sort. Se la memoria è la costrizione, heap sort e quick sort. Se non puoi permetterti un caso peggiore quadratico, né quick sort con pivot fisso né bubble sort. Nessun algoritmo vince su tutte le righe, ed è per questo che un ordinamento di libreria è quasi sempre un ibrido.

L'ordinamento di Python: sfrutta l'ordine che c'è già

La funzione sorted di Python usa Timsort, un merge sort stabile che cerca nell'ingresso sequenze già ordinate (run) e le fonde. Le note di implementazione, in Objects/listsort.txt, dichiarano che servono meno di lg(N!) confronti sui dati parzialmente ordinati e «as few as N-1». Il listato lo verifica con una classe che conta le chiamate a __lt__.

# L'ordinamento di Python: si contano i confronti con una classe che li registra in __lt__
import math, random

class Counted:
    calls = 0
    def __init__(self, k): self.k = k
    def __lt__(self, other):
        Counted.calls += 1
        return self.k < other.k

def count(keys):
    Counted.calls = 0
    sorted(Counted(k) for k in keys)
    return Counted.calls

rng = random.Random(5)
print(f"{'n':>5} {'ordinato':>9} {'inverso':>9} {'tutti uguali':>13} {'casuale (media 10)':>19} {'ceil(lg n!)':>12}")
for n in (64, 512, 4096):
    asc = count(range(n))
    desc = count(range(n, 0, -1))
    same = count([7] * n)
    avg = sum(count(rng.sample(range(n), n)) for _ in range(10)) / 10
    print(f"{n:>5} {asc:>9} {desc:>9} {same:>13} {avg:>19.0f} {math.ceil(math.log2(math.factorial(n))):>12}")

# Output:
#     n  ordinato   inverso  tutti uguali  casuale (media 10)  ceil(lg n!)
#    64        63        63            63                 304          296
#   512       511       511           511                3965         3876
#  4096      4095      4095          4095               43988        43251

Ordinato, inverso e tutto uguale costano esattamente n − 1 confronti (4.095 per n = 4.096): una sola scansione basta a riconoscere una run, anche se decrescente. Sull'ingresso casuale il costo è fra l'1,7% e il 2,7% sopra il limite ⌈lg n!⌉ (43.988 contro 43.251), quindi su dati senza struttura non perde quasi nulla rispetto al meglio possibile. È un risultato che non otterresti con nessuno dei quattro algoritmi in versione manualistica: per i dati reali, che hanno quasi sempre un po' di ordine, un ibrido adattivo è la scelta di libreria sensata. Sulla stabilità e sul key trovi le garanzie esatte nella guida di Python.

Quando il limite n log n non vale: counting sort

Il limite ⌈lg n!⌉ riguarda gli ordinamenti che confrontano elementi. Se le chiavi sono interi in un intervallo noto [0, k) si può ordinare senza confronti: si conta quante volte compare ogni valore, si calcola da quale posizione parte ciascun valore e si piazzano gli elementi. Il listato conta le operazioni e le confronta con 2n + k.

# Counting sort: nessun confronto fra elementi. Funziona solo se le chiavi sono interi in [0, k)
import random

def counting_sort(a, k):
    ops = 0
    count = [0] * k
    for x in a:                              # 1) istogramma: n passi
        count[x] += 1; ops += 1
    pos, total = [0] * k, 0
    for v in range(k):                       # 2) posizioni di partenza: k passi
        pos[v] = total; total += count[v]; ops += 1
    out = [None] * len(a)
    for x in a:                              # 3) piazzamento in ordine di arrivo: n passi, stabile
        out[pos[x]] = x; pos[x] += 1; ops += 1
    return out, ops

rng = random.Random(6)
for _ in range(3000):
    k = rng.randrange(1, 12)
    a = [rng.randrange(k) for _ in range(rng.randrange(0, 50))]
    assert counting_sort(a, k)[0] == sorted(a)
print("counting sort: corretto su 3000 casi")

print(f"{'n':>7} {'k':>7} {'operazioni':>11} {'2n + k':>9}")
for n, k in ((1000, 10), (1000, 1000), (1000, 100000), (100000, 10)):
    a = [rng.randrange(k) for _ in range(n)]
    out, ops = counting_sort(a, k)
    assert out == sorted(a)
    print(f"{n:>7} {k:>7} {ops:>11} {2 * n + k:>9}")

# Output:
# counting sort: corretto su 3000 casi
#       n       k  operazioni    2n + k
#    1000      10        2010      2010
#    1000    1000        3000      3000
#    1000  100000      102000    102000
#  100000      10      200010    200010

Le operazioni coincidono con 2n + k in ogni riga: due passaggi sull'ingresso e uno sull'intervallo. Con mille chiavi in [0, 1.000) sono 3.000 operazioni, molte meno degli almeno 8.530 confronti (⌈lg 1000!⌉) che servono a un ordinamento per confronti; ma con le stesse mille chiavi in [0, 100.000) diventano 102.000, perché paga l'intervallo e non gli elementi. Il piazzamento in ordine di arrivo lo rende stabile, ed è per questo che si usa come passo base del radix sort. Funziona solo con chiavi intere limitate: su stringhe lunghe o numeri reali torni agli ordinamenti per confronti.

Esercizi

1. Togli l'uscita anticipata da bubble sort e verifica che il caso già ordinato costa n(n − 1)/2 confronti.
2. Sostituisci < con <= nella fusione di merge sort e trova un ingresso da due elementi su cui il confronto con sorted fallisce.
3. Cambia il pivot di quick sort in «mediano di tre» (primo, centrale, ultimo) e costruisci un ingresso su cui costa comunque molto più di n lg n.
4. Scrivi un ordinamento stabile basato su heap, aggiungendo l'indice di arrivo alla chiave, e conta quanti confronti in più costa.

Il primo esercizio chiude il ragionamento su bubble sort, il secondo ti fa vedere una stabilità persa per un solo carattere. Nel terzo non c'è una risposta unica: esistono ingressi avversari per ogni regola fissa di scelta del pivot, e trovarne uno è il modo più rapido di capire perché si randomizza.

Domande frequenti

Quale algoritmo di ordinamento è il più veloce?

Non esiste: dipende dall'ingresso e dai vincoli. Nel caso peggiore nessun ordinamento per confronti scende sotto ⌈log₂ n!⌉ confronti, e merge sort e heap sort ci stanno vicini; in pratica, per dati reali, un ibrido adattivo come Timsort è spesso la scelta migliore.

Perché quick sort può diventare quadratico?

Perché se il pivot cade sempre vicino a un estremo, ogni partizione elimina un solo elemento. Con il pivot all'ultimo posto su una lista già ordinata i confronti sono n(n − 1)/2; con un pivot casuale quel caso non si può più costruire in anticipo.

Che cosa significa che un ordinamento è stabile?

Significa che due elementi con la stessa chiave restano nell'ordine in cui erano. È indispensabile quando ordini per più campi in successione; sorted di Python lo garantisce, quick sort e heap sort no.

Che cosa sai fare adesso

Sai scrivere i quattro ordinamenti classici e provarne la correttezza su tutti gli ingressi piccoli, sai costruire il caso peggiore di ciascuno e confrontarlo con la formula, e sai leggere un conteggio di confronti rispetto al limite ⌈lg n!⌉. Sai anche scegliere in base a ciò che ti serve davvero, stabilità, memoria o garanzia sul caso peggiore, e sai che un ordinamento senza confronti esiste quando le chiavi sono interi limitati. Nell'articolo successivo cerchi invece un elemento: ricerca lineare, binaria e tabelle hash, che presuppone proprio una lista ordinata.

Nella stessa serie trovi anche il riepilogo sulla programmazione dinamica.