Algoritmi di ordinamento

Problema: disporre gli elementi di una lista in ordine non decrescente. Tutti gli algoritmi qui sotto ordinano per confronti (<, <=), quindi funzionano con numeri, stringhe, tuple.

Proprietà da considerare:

Definizione (proprietà degli algoritmi di ordinamento)

• costo nel caso peggiore, migliore, medio (vedi Complessità computazionaleCosto di un algoritmo in funzione della dimensione dell'input; caso peggiore, migliore e medio; notazione O-grande e classi di crescita; come contare i passi di cicli e ricorsioni; costo delle operazioni Python.Complessità computazionale →);
• sul posto (in place): usa solo $O(1)$ memoria aggiuntiva;
• stabile: elementi uguali restano nell'ordine relativo di partenza (conta quando si ordina per una chiave, es. studenti per voto).

Esempio. Ordinando [("b", 1), ("a", 1)] per il secondo campo con un algoritmo stabile, ("b", 1) resta prima di ("a", 1).

Selection sort

A ogni passo i si cerca il minimo di v[i:] e lo si scambia con v[i].

def selection_sort(v):
    n = len(v)
    for i in range(n - 1):
        im = i
        for j in range(i + 1, n):
            if v[j] < v[im]:
                im = j
        v[i], v[im] = v[im], v[i]

Proprietà (selection sort)

• Invariante: v[:i] contiene gli i elementi più piccoli, in ordine.
• Confronti: $n(n-1)/2$ sempre → $O(n^2)$ in tutti i casi. Al più $n - 1$ scambi.
• Sul posto, non stabile.

Esempio. Con v = [5, 2, 4] il selection sort esegue $3\cdot2/2=3$ confronti e porta v a [2, 4, 5].

Insertion sort

Si scorre la lista; ogni elemento viene inserito al posto giusto nella parte iniziale già ordinata, spostando a destra i maggiori.

def insertion_sort(v):
    for i in range(1, len(v)):
        x = v[i]
        j = i - 1
        while j >= 0 and v[j] > x:
            v[j + 1] = v[j]
            j -= 1
        v[j + 1] = x

Proprietà (insertion sort)

• Invariante: v[:i] è ordinata (ma contiene gli elementi originali di v[:i], non i più piccoli).
• Caso peggiore (lista al contrario) $O(n^2)$; caso migliore (già ordinata) $O(n)$: molto buono su liste quasi ordinate.
• Sul posto, stabile (grazie a > stretto nel while).

Esempio. L'insertion sort su [1, 2, 3, 4] esegue $3$ confronti ($O(n)$), su [4, 3, 2, 1] ne esegue $6$ ($O(n^2)$).

Bubble sort

Si scorrono le coppie adiacenti scambiando quelle fuori ordine; dopo il passo k gli ultimi k elementi sono definitivi. Con un flag ci si ferma se in un passo non ci sono scambi.

def bubble_sort(v):
    n = len(v)
    for k in range(n - 1):
        scambi = False
        for j in range(n - 1 - k):
            if v[j] > v[j + 1]:
                v[j], v[j + 1] = v[j + 1], v[j]
                scambi = True
        if not scambi:
            break

Proprietà (bubble sort). $O(n^2)$ nel caso peggiore, $O(n)$ se già ordinata; sul posto e stabile. Più lento di insertion sort in pratica.

Esempio. Con il flag, bubble_sort([1, 2, 3]) si ferma dopo un solo passo di $2$ confronti: costo $O(n)$.

Merge sort

Divide et impera (RicorsioneFunzioni che chiamano se stesse: caso base e passo ricorsivo, stack delle chiamate, esempi su numeri, stringhe e liste, ricorsione multipla e suo costo, divide et impera, confronto con l'iterazione.Ricorsione →): si divide la lista a metà, si ordinano ricorsivamente le due metà, si fondono le due metà ordinate (fusione con due indici, vedi Pattern algoritmici iterativiSchemi ricorrenti nei cicli: accumulatore, contatore, massimo e minimo, ricerca con uscita anticipata, verifica universale, filtro e trasformazione, finestra scorrevole, due indici, elaborazione di coppie.Pattern algoritmici iterativi →).

def merge_sort(v):
    if len(v) <= 1:
        return v
    m = len(v) // 2
    a = merge_sort(v[:m])
    b = merge_sort(v[m:])
    # fusione
    out, i, j = [], 0, 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:        # <= rende l'algoritmo stabile
            out.append(a[i]); i += 1
        else:
            out.append(b[j]); j += 1
    out.extend(a[i:])
    out.extend(b[j:])
    return out

Proprietà (merge sort: costo e memoria)

• Costo $T(n) = 2T(n/2) + O(n)$ → $O(n \log n)$ in tutti i casi: $\log_2 n$ livelli di ricorsione, ciascuno con lavoro complessivo $O(n)$ per le fusioni.
• Memoria aggiuntiva $O(n)$ (non sul posto); stabile.
• Questa versione restituisce una lista nuova: v = merge_sort(v).

Esempio. merge_sort([5, 2, 4, 1]) restituisce [1, 2, 4, 5], con $\log_24=2$ livelli di divisione.

Confronto

Teorema (limite inferiore per l'ordinamento per confronti). Nessun ordinamento per confronti può fare meglio di $O(n \log n)$ nel caso peggiore.

Esempio. Per ordinare $n=1000$ elementi servono nel caso peggiore almeno $\log_21000!\approx8529$ confronti.

In Python: sort e sorted

Definizione (sort e sorted in Python). Nella pratica si usa l'ordinamento predefinito (Timsort: $O(n \log n)$, stabile, $O(n)$ su dati già ordinati).

v.sort()                                  # sul posto, restituisce None
w = sorted(v)                             # nuova lista
sorted(v, reverse=True)                   # decrescente
sorted(parole, key=str.lower)             # ignorando maiuscole/minuscole
sorted(studenti, key=lambda s: (-s[1], s[0]))   # voto decrescente, poi nome

Esempio. sorted([3, 1, 2], reverse=True) restituisce [3, 2, 1] e sorted(["b", "A", "c"], key=str.lower) restituisce ['A', 'b', 'c'].

key è una funzione applicata a ogni elemento: si confrontano i risultati. La stabilità permette ordinamenti a più livelli in passaggi successivi.

Errori tipici

• v = v.sort() (vedi Liste in Pythonlist come sequenza mutabile (array dinamico); indici, slicing e assegnamento a fette; metodi e loro costo; aliasing, copia superficiale e profonda; list comprehension; liste annidate e matrici.Liste in Python →).
• Nell'insertion sort, controllare v[j] > x prima di j >= 0: con j = -1 si legge v[-1] (l'ultimo elemento) invece di fermarsi.
• Merge sort che fonde senza aggiungere i residui (extend) di una delle due metà.