Unplugged: SORT! Come mettere in fila tutto e vivere felici

Gli algoritmi di sorting, che passione! Qui i giovani programmatori cominciano a vedere che le cose si possono fare in molti modi diversi; non esiste quasi mai LA soluzione, ma certe soluzioni sono mooolto migliori di altre, specie quando il gioco si fa duro.

Ecco qui un po’ di appunti per fare un’oretta di body sorting :-D

Useremo dei cartoncini (o un A4 piegato in 2 per dargli un po’ più di consistenza) da tenere sul petto con un cordoncino che passa dietro al collo. Ci metteremo su un numero di 2 cifre per semplicità. Vogliamo che i bambini trovino dei sistemi per mettersi in fila per numeri crescenti. Faremo prima una prova libera dove ognuno si muove liberamente confrontando il proprio numero con quello degli altri e caoticamente trova il suo posto nella fila. Saranno straordinariamente efficienti! Ma questa è intelligenza distribuita…

Quello che ci serve, quello che i bambini devono trovare, invece, è una precisa sequenza di istruzioni (un algoritmo!) che il mentor dovrà seguire (come fossero mattoncini di Scratch) per dare un unico tipo di ordine esecutivo ai bambini: tu … vai al posto di … e viceversa; non esistono altri ordini; esistono invece i SE, i RIPETI e le condizioni vero/falso: ad esempio il numero di … è più piccolo di quello di … (o è vero o è falso: se i numeri sono uguali viene falso

Meglio evitare numeri doppi nei cartoncini: si semplificano gli algoritmi.

Bisogna contare quanti scambi di posto mediamente ci vogliono per mettere in fila 6/7 bambini (4 gruppi) e poi 12/13 e infine tutti e venticinque. Useremo il computer che proietta a muro per tener dietro agli esperimenti.

Il mentor può indirizzare i bambini verso un paio di algoritmi classici:

Bubble sort

Si tratta dell’algoritmo più semplice: i bambini si mettono in fila in ordine casuale. Partendo dal secondo bambino e proseguendo fino all’ultimo il mentor lo fa scambiare col bambino precedente se sono fuori sequenza (cioè se il bambino precedente ha un numero più grande). Si contano gli scambi. Dopo aver considerato anche l’ultimo bambino, cioè dopo aver esaminato l’intera fila, il mentor si chiede se ha eseguito ZERO scambi: se sì allora significa che la fila è ordinata e abbiamo finito; se no si accumulano in un contatore generale gli scambi effettuati e si ricomincia sempre dal secondo bambino.

Non è un algoritmo efficiente: dobbiamo aspettarci una crescita quadratica degli scambi in funzione della grandezza del gruppo: da 6 x 6 = 36 (fattibile) a 25 x 25 = 625 scambi (qui ci stufiamo prima e cambiamo algoritmo)

Una variante (che però non migliorano l’efficienza) consiste nel trovare il più piccolo elemento ad ogni giro (confrontando sempre con il primo bambino, non con il bambino precedente) e diminuire la dimensione della fila da controllare ad ogni giro: siccome abbiamo trovato il più piccolo, infatti, quello non lo consideriamo più perché non lo muoveremo più da lì; per questo il “primo bambino della fila da esaminare” dopo un giro diventa il secondo, poi il terzo, etc etc fino ad arrivare ad ignorare il penultimo bambino e l’ordinamento è completo :-)

Quick sort

Divide et impera! Sortiamo una fila tagliandola in due, e poi tagliando in due le due metà… fino ad arrivare a sotto file da un solo bambino che sono ordinate “per forza”. Ecco come si fa: ci vuole calma e tanta attenzione ;-)

Prendiamo il primo bambino della fila e consideriamo il suo numero, ad esempio 42. Adesso vogliamo fare due sotto file: una con i numeri più piccoli o uguali a 42 (che metteremo all’inizio della fila originale) e l’altra con gli altri (più grandi di 42). Bene: partiamo dall’ultimo bambino e proseguiamo (verso il primo) finché non troviamo un bambino con il numero “sbagliato da quella parte”, cioè più piccolo (o uguale a) 42. Quel bambino alza la mano e resta lì. Al limite arriviamo al primo bambino!

Adesso partiamo dal primo bambino e proseguiamo verso il bambino con la mano alzata finché non lo oltrepassiamo, oppure troviamo un bambino con il numero “sbagliato da quella parte”, cioè più grande di 42. Se lo trovo allora anche lui alza la mano e si scambia con l’altro. Poi tutto ricomincia sui bambini che sono rimasti “all’interno” dei due bimbi scambiati (ecco perché è importante che restino almeno per un po’ con le mani alzate).

Alla fine tutti i bambini saranno stati “esaminati” cioè confrontati con il numero 42, eventualmente scambiati con il loro omologo e avremo oltrepassato “salendo” un bambino con la mano alzata. A questo punto possiamo fermarci e osservare che possiamo dividere in due la fila: il primo pezzo ha solo bambini con numeri più piccoli di (o uguali a 42), mentre il resto ha solo bambini con numeri più grandi di 42. Vero? Se abbiamo avuto sfortuna allora 42 era il numero più grande di tutti e quindi abbiamo sprecato un giro: può capitare, ma bisogna insistere fino alla fine, con fiducia, e le cose vanno a posto.

Molto probabilmente i bambini non sono in ordine, dentro queste 2 sotto file, ma intanto abbiamo diviso il problema in due: quando le 2 file saranno in ordine al loro interno allora potremo attaccarle insieme e avremo risolto tutto! Divide et impera!

Credo sia bene allontanare tra loro le due sotto file, in modo che non si crei confusione. Inoltre nella prima fila (quella che ha al primo posto il 42) dobbiamo ricordarci di scambiare subito il primo bambino (che per definizione ha il numero più grande) con l’ultimo. Questo scambio è fondamentale! Non dimentichiamocelo.

Adesso siamo pronti a ripetere recursivamente il quicksort dentro le 2 sotto file. E avanti e avanti finché non si arriva a sotto file da 1 o 2 bambini, ordinate/bili immediatamente. Poi tutti i bambini si riavvicinano, si prendono per mano e… quicksort completato! Con molti meno scambi del bubble sort (n log n, mediamente, invece di n quadro).

Merge sort

Se il quicksort coreograficamente è poco pratico, pensavo che si potrebbe fare una specie di merge sort: il primo bambino della fila (che ha un numero a caso, ad esempio… 42! ;-) va al centro della sala. Tutti gli altri bambini gli si presentano davanti: quelli con numeri inferiori vanno a sinistra e gli altri a destra. Ed ecco facilmente costituite le 2 sotto file. Il bambino col 42 (quello che adesso è al centro della sala) va a fare l’ultimo della fila di sinistra. Da capo: il primo di ogni sotto lista va al centro della sala, gli altri sfilano e vanno di qua o di là… anche qui di arriva rapidamente a micro liste ordinate e poi si può ricominciare ad attaccarsi.

Col merge sort si cammina ben di più… e non si sa bene come conteggiare gli scambi. Però è un bell’esempio di un’altra soluzione efficiente come tempi anche se qui c’è bisogno di più spazio.

Conclusioni

Credo sia importante che i mentor facciano capire la furbata di dividere il problema in sotto problemi via via più semplici, fino ad essere triviali. Se ad esempio partiamo con 1000 (mille!) bambini e cominciamo a dividere per 2, in dieci passaggi arriviamo a un singolo bambino, per dire. Certo, col quick e il merge sort non ci si può aspettare che le sotto file vengano sempre la metà esatta: il caso ci mette del suo, ma… sicuramente andiamo molto ma molto più in fretta che col bubble. Anche se il bubble è più simpatico ;-) finché non pensi al milione di scambi che ti può costare!