Algoritmi di ordinamento: bubble, selection e insertion sort

Se sei in terza al liceo scientifico, opzione scienze applicate, e a ottobre in informatica avete finito (o state finendo) cicli e array, gli algoritmi di ordinamento sono il passo successivo: di solito arrivano tra ottobre e novembre, e la verifica che li contiene cade fra sei e nove settimane. C’è tempo per capirli davvero, invece di impararli a memoria. Se ti manca la base sugli array, parti da cicli e array; per il costo degli algoritmi in generale c’è la complessità con la notazione O-grande, qui la tocco solo in modo intuitivo.

L’idea in una riga ciascuno

Dobbiamo ordinare un array in modo crescente. Tre strategie, tutte basate su confronti e scambi:

• Bubble sort: confronta coppie adiacenti e le scambia se sono nell’ordine sbagliato. A ogni passata il valore più grande “sale” in fondo, come una bolla.
• Selection sort: a ogni passata cerca il minimo della parte non ancora ordinata e lo porta nella prima posizione libera.
• Insertion sort: tiene ordinata la parte sinistra e inserisce, uno alla volta, l’elemento successivo nel posto giusto, come quando ordini le carte in mano.

Traccia su un array di 6 elementi

Useremo sempre $[5,2,4,6,1,3]$. Le tracce a mano sono ciò che ti chiedono in verifica, quindi leggile con la matita in mano.

Bubble sort

Passata 1 (5 confronti): $(5,2)$ scambio → $[2,5,4,6,1,3]$; $(5,4)$ scambio → $[2,4,5,6,1,3]$; $(5,6)$ no; $(6,1)$ scambio → $[2,4,5,1,6,3]$; $(6,3)$ scambio → $[2,4,5,1,3,6]$. Il 6 è al suo posto definitivo.

Passata 2 (4 confronti): $(2,4)$ no; $(4,5)$ no; $(5,1)$ scambio; $(5,3)$ scambio → $[2,4,1,3,5,6]$.

Passata 3 (3 confronti): $(2,4)$ no; $(4,1)$ scambio; $(4,3)$ scambio → $[2,1,3,4,5,6]$.

Passata 4 (2 confronti): $(2,1)$ scambio → $[1,2,3,4,5,6]$; $(2,3)$ no.

Passata 5 (1 confronto): $(1,2)$ no. Totale: 15 confronti e 9 scambi.

Selection sort

• $i=0$: il minimo di tutto l’array è 1 (posizione 4); scambio con il 5 → $[1,2,4,6,5,3]$.
• $i=1$: il minimo di $[2,4,6,5,3]$ è 2, già al suo posto; niente scambio.
• $i=2$: il minimo di $[4,6,5,3]$ è 3; scambio con il 4 → $[1,2,3,6,5,4]$.
• $i=3$: il minimo di $[6,5,4]$ è 4; scambio con il 6 → $[1,2,3,4,5,6]$.
• $i=4$: il minimo di $[5,6]$ è 5, già al suo posto.

Totale: 15 confronti e 3 scambi (al massimo $n-1=5$).

Insertion sort

Qui si “spostano” elementi verso destra per fare spazio, poi si inserisce la chiave $k$.

• $k=2$: il 5 è maggiore, si sposta → $[2,5,4,6,1,3]$ (1 spostamento).
• $k=4$: il 5 si sposta, il 2 no → $[2,4,5,6,1,3]$ (1).
• $k=6$: il 5 non è maggiore di 6, resta dov’è (0).
• $k=1$: si spostano 6, 5, 4, 2, poi 1 va in testa → $[1,2,4,5,6,3]$ (4).
• $k=3$: si spostano 6, 5, 4, il 2 no → $[1,2,3,4,5,6]$ (3).

Totale: 12 confronti e 9 spostamenti. Il 9 non è un caso: coincide con il numero di scambi del bubble sort, perché entrambi eliminano una per una le inversioni, cioè le coppie in cui un elemento più grande sta prima di uno più piccolo. In $[5,2,4,6,1,3]$ sono $4+1+2+2=9$.

Pseudocodice e Python

Bubble sort, in pseudocodice:

per i da 0 a n-2:
    per j da 0 a n-2-i:
        se a[j] > a[j+1]:
            tmp = a[j]
            a[j] = a[j+1]
            a[j+1] = tmp

In Python lo scambio si può scrivere in una riga, ma capire la versione con tmp serve in tutti gli altri linguaggi:

def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]

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

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

Quando passi un array a una funzione che lo modifica, ricorda come funziona il passaggio dei parametri: ne parlo in valore e riferimento.

Perché sono O(n²) e quale scegliere

In tutti e tre ci sono due cicli annidati. Il ciclo esterno gira circa $n$ volte e l’interno, in media, circa $n/2$: i confronti sono dell’ordine di

Per $n=6$ fa 15, ed è proprio il numero che abbiamo contato. Se raddoppi $n$ i confronti diventano circa quattro volte tanti: è il significato intuitivo di $O(n^2)$.

Quale scegliere:

Nel bubble sort puoi aggiungere un controllo: se in una passata non avviene nessuno scambio, l’array è già ordinato e ti fermi. Su un array già ordinato fa solo $n-1$ confronti.

Gli errori che vedo di più

Limiti dei cicli sbagliati. Nel bubble sort l’indice interno arriva a $n-2-i$ (in Python range(n-1-i)) perché dentro il ciclo si legge a[j+1]: con un limite di troppo si esce dall’array. Allo stesso modo il ciclo esterno non deve arrivare a $n$. Nel selection sort il ciclo interno parte da $i+1$, non da $i$, altrimenti confronti l’elemento con se stesso.

Scambio senza variabile temporanea. Scrivere a[j] = a[j+1] e subito dopo a[j+1] = a[j] copia lo stesso valore due volte e il valore originale di a[j] è perso.

Confondere selection e bubble. Il selection sort cerca prima il minimo e poi scambia una volta; il bubble scambia durante la scansione.

Dimenticare lo spostamento dell’insertion sort. Se non salvi la chiave $k$ prima di spostare gli elementi, la sovrascrivi.

Tre esercizi svolti

1. Caso peggiore del bubble sort

Conta confronti e scambi del bubble sort su $[4,3,2,1]$.

Passata 1: $(4,3)$, $(4,2)$, $(4,1)$ sono tre confronti e tre scambi → $[3,2,1,4]$. Passata 2: $(3,2)$ e $(3,1)$, due scambi → $[2,1,3,4]$. Passata 3: $(2,1)$, uno scambio → $[1,2,3,4]$. Totale: $3+2+1=6$ confronti e $3+2+1=6$ scambi, cioè tutte le 6 coppie sono inversioni. Con l’array già ordinato $[1,2,3,4]$ e il controllo di uscita anticipata, invece, 3 confronti e 0 scambi.

2. Quanto cresce il costo

Quanti confronti servono per ordinare 10, 100 e 1000 elementi con il selection sort? E 2000?

Per 2000: $\frac{2000\cdot 1999}{2}=1999000$, circa 4 volte i 499 500 di prima: raddoppiando $n$ il costo quadruplica. Moltiplicare $n$ per 10 moltiplica i confronti per circa 100.

3. Trova l’errore

Questo bubble sort in un linguaggio senza scambio multiplo ha due errori. Quali?

per j da 0 a n-1-i:
    se a[j] > a[j+1]:
        a[j] = a[j+1]
        a[j+1] = a[j]

Primo errore: con $j$ fino a $n-1-i$, quando $i=0$ si arriva a $j=n-1$ e si legge a[n], fuori dall’array; il limite corretto è $n-2-i$. Secondo errore: lo scambio. Con $a=[7,3]$, la prima assegnazione dà $[3,3]$ e la seconda lo lascia $[3,3]$: il 7 è sparito. Serve tmp = a[j] prima della prima assegnazione e a[j+1] = tmp alla fine.

Metti alla prova

Per allenarti sul ragionamento a tempo puoi usare i simulatori per il liceo. Per informatica non c’è ancora una simulazione dedicata: i quesiti che trovi riguardano matematica e fisica. Un buon modo per prepararti è rifare le tre tracce senza guardare, cambiando l’array. Altre risorse sono nella pagina informatica; se ti serve una mano, faccio ripetizioni 1-a-1 online e puoi partire da una diagnosi gratuita. Vicino a questo argomento c’è anche la ricorsione, che di solito segue gli ordinamenti.