Esercizio 4ordinamento con scambi, traccia e invariante

for i <- 0 to n-2 do
    for j <- i+1 to n-1 do
        if (S[j] < S[i]) then swap(S[i], S[j])

---

(a) Traccia

Si confronta $S[i]$ con ogni elemento successivo e, se ne trova uno minore, lo scambia con la posizione $i$. Alla fine del ciclo interno $S[i]$ contiene quindi il minimo di $S[i..n-1]$.

Ad esempio per $i = 0$: $S[1] = 1 < 12$ scambia ($1, 12, \dots$); gli altri non sono minori di $1$. Per $i = 1$ ($S[1] = 12$): $14, 10 < 12$? $14$ no; $10 < 12$ scambia $\to 1, 10, 14, 12, 8, 5$; $8 < 10$ scambia $\to 1, 8, 14, 12, 10, 5$; $5 < 8$ scambia $\to 1, 5, 14, 12, 10, 8$. (Tracce verificate eseguendo il codice.)

(b) Cosa fa e invariante

L'algoritmo ordina $S$ in senso crescente. È una variante del selection sort (vedi Algoritmi di ordinamentoSelection sort e insertion sort (quadratici, con invarianti), merge sort (divide et impera, Theta(n log n)), quick sort (caso pessimo quadratico, medio n log n), heap sort (in loco, Theta(n log n)), ordinamento senza confronti per chiavi intere in un intervallo piccolo, limite inferiore Omega(n log n) per gli algoritmi basati su confronti.Algoritmi di ordinamento →) che, invece di scegliere l'indice del minimo e fare uno scambio, scambia ogni volta che trova un elemento minore: più scambi, stessi $\frac{n(n-1)}{2}$ confronti.

Invariante del ciclo esterno (all'inizio dell'iterazione $i$, e alla fine dell'iterazione $i-1$): $S[0..i-1]$ contiene i $i$ elementi più piccoli di $S$, in ordine crescente; di conseguenza $S[0] \le \dots \le S[i-1] \le S[k]$ per ogni $k \ge i$.

• Inizio ($i = 0$): il prefisso è vuoto.
• Conservazione. L'iterazione $i$ porta in $S[i]$ il minimo di $S[i..n-1]$. Infatti (invariante del ciclo interno): dopo l'iterazione $j$, $S[i]$ è il minimo di $S[i..j]$ originali dell'iterazione e il multiset $S[i..n-1]$ non cambia. Base: prima del ciclo interno $S[i]$ è il minimo di $S[i..i]$. Passo: se $S[j] < S[i]$ si scambiano e $S[i]$ diventa il nuovo minimo; altrimenti $S[i]$ resta minimo di $S[i..j]$. Alla fine $S[i] = \min S[i..n-1]$: aggiunto al prefisso, che per ipotesi contiene i più piccoli e ha tutti gli elementi $\le$ quelli di $S[i..n-1]$, mantiene l'invariante con $i + 1$ elementi.
• Uscita: dopo $i = n - 2$ il prefisso $S[0..n-2]$ contiene i $n - 1$ elementi più piccoli ordinati e l'ultimo, $S[n-1]$, è per forza il massimo: la sequenza è ordinata.

Errori comuni

• Dimenticare che dopo l'iterazione $i$ non solo $S[i]$ è al suo posto, ma tutto $S[0..i]$ contiene i più piccoli: l'invariante riguarda anche i valori e non solo l'ordine relativo.
• Scrivere un invariante valido solo alla fine del ciclo esterno.
• Pensare che il resto della sequenza ($S[i..n-1]$) resti nell'ordine originale: dopo gli scambi viene rimescolato.