Giusto, poi veloce

Un algoritmo sbagliato O(1) resta sbagliato.

Il disegno

Gira finché la condizione di uscita è vera. Se l’invariante regge, il risultato è difendibile.

invariante

pezzo selezionato

Prima

Array non nullo? Ordinato? Chiavi uniche? Se non lo dici, l’algoritmo è un racconto.

Da ricordare

Precondizione = contratto. Come i tipi, ma per i dati.

Invariante: cosa resta vero a ogni passo. Esempio: “tutto a sinistra dell’indice è già ordinato”.

Testa i bordi: vuoto, un elemento, duplicati, già ordinato, inversamente ordinato. I PDF amano i casi felici. I bug no.

Disegna questo

Un ciclo con una scritta sopra che non cambia mai (invariante). Due caselle: input vuoto / input enorme.

Un foglio, non un software. Se lo sai ridisegnare senza guardare, la lezione è tua.