Un array è una sequenza di valori. Ordinare l’array significa disporli, per esempio, dal più piccolo al più grande. Il risultato può essere identico anche se il percorso cambia molto. Consideriamo sempre il piccolo array [5, 2, 4, 1] e poi proviamo i tre metodi sui 12 elementi del laboratorio visuale.
Prima di iniziare: confronto e scambio
Un confronto risponde a una domanda come «5 è maggiore di 2?». Uno scambio cambia la posizione di due elementi. Nel laboratorio ogni confronto e ogni scambio è un passo visibile; il tempo di animazione non coincide con la velocità reale del computer.
Bubble Sort: il maggiore sale in fondo
Si confrontano due vicini da sinistra a destra. Se il primo è maggiore del secondo, si scambiano. Alla fine di una passata il valore maggiore della parte ancora da ordinare è arrivato a destra; nelle passate successive non occorre più toccarlo.
- Da [5, 2, 4, 1]: 5 e 2 si scambiano → [2, 5, 4, 1].
- 5 e 4 si scambiano → [2, 4, 5, 1]. Poi 5 e 1 si scambiano → [2, 4, 1, 5]. Ora 5 è al suo posto.
- Nella seconda passata 2 e 4 restano, 4 e 1 si scambiano → [2, 1, 4, 5].
- Nell’ultima passata 2 e 1 si scambiano → [1, 2, 4, 5].
È facile da seguire ma, su array grandi, può richiedere molti confronti e molti scambi. Se una passata non produce alcuno scambio, si può terminare subito.
Selection Sort: cerca il minimo
Si divide idealmente l’array in una parte già ordinata a sinistra e una ancora da ordinare a destra. Si cerca il minimo della parte destra, poi lo si mette nella prima posizione libera mediante uno scambio. La parte ordinata cresce di un elemento.
- In [5, 2, 4, 1] il minimo è 1. Si scambiano 5 e 1 → [1, 2, 4, 5].
- Tra [2, 4, 5] il minimo è già 2: non serve scambiare.
- Tra [4, 5] il minimo è già 4. Il risultato è [1, 2, 4, 5].
Il numero di confronti resta elevato anche se l’array è già ordinato, ma gli scambi sono al massimo uno per posizione.
Insertion Sort: inserisci nella parte ordinata
Il primo elemento da solo è già ordinato. Si prende il successivo e lo si porta verso sinistra finché trova la posizione corretta nella parte iniziale ordinata. In questo laboratorio lo spostamento è mostrato come una serie di scambi fra vicini.
- Si parte da [5]. Inserendo 2 prima di 5 si ottiene [2, 5, 4, 1].
- Si inserisce 4 fra 2 e 5 → [2, 4, 5, 1].
- Si inserisce 1 prima di tutti → [1, 2, 4, 5].
Funziona particolarmente bene quando i valori sono già quasi ordinati: ogni nuovo elemento deve percorrere poca strada.
Che cosa cambia davvero?
I tre metodi ordinano correttamente, ma compiono operazioni diverse. Bubble Sort confronta vicini in più passate; Selection Sort cerca ogni volta il minimo e limita gli scambi; Insertion Sort costruisce progressivamente una parte ordinata. Nel caso peggiore, per tutti e tre, confronti e spostamenti crescono all’incirca con il quadrato della dimensione dell’array. Su 12 valori è più utile osservare il perché di ogni mossa che misurare i millisecondi.