Ordiniamo le bolle
Parliamo del famoso Bubble sort che ci permette di ordinare in maniera semplice e abbastanza veloce una lista di elementi spostando quelli più grandi verso un lato della lista e i più piccoli dall'altro. In questo modo i vari elementi risaliranno la lista o scenderanno proprio come se fossero delle bollicine spumeggianti.
Vediamo brevemente il funzionamento. Per ogni coppia di elementi della lista andiamo a controllare se il primo elemento selezionato è maggiore del secondo, in caso positivo verranno scambiati di posto facendo risalire il più piccolo e scendere il più grande, parliamo di posizioni all'interno della lista. Avremo quindi gli elementi più piccoli verso l'inizio della lista (più leggeri verso l'alto) e quelli più grandi verso la fine della lista (le bolle più pesanti sul fondo).
Ho inserito per comodità il codice all'interno di una procedura per poterlo richiamare all'occorrenza, voi potrete inserirlo dove più vi piace.
La prima cosa che salta subito all'occhio dopo l'inizializzazione delle variabili è la presenza di due cicli annidati da cui comprendiamo che alcune operazioni si ripeteranno più volte per più passaggi e qui ritroviamo anche la bellezza di questo metodo.
All'interno del secondo ciclo (quello più interno) possiamo notare che ho legato il numero di ripetizioni non solo alla lunghezza della lista , che quindi varierà automaticamente a seconda della lista usata, ma anche al passaggio che stiamo effettuando (n. passaggio).
Cosa significa. Ad ogni nuovo passaggio non andremo a controllare tutti gli elementi della lista ma salteremo quelli già posizionati andando quindi a risparmiare tanti passaggi quanto più lunga è la lista, ottimizzando tempo e risorse.
Il ciclo più interno è quello che serve per scorrere tutti gli elementi , partirà da un numero di volte pari alla lunghezza della lista meno un elemento, lavoriamo con le coppie quindi l'ultimo passaggio controlla ultimo e penultimo insieme, e diminuirà di un'unità ad ogni nuovo "giro".
Per scorrere la lista andremo a cambiare di 1 le variabili i e j ad ogni passaggio e controllando ogni volta se l'elemento i-esimo > j-esimo , quindi se il primo elemento della coppia e maggiore del secondo , invertendo la loro posizione se questa condizione è verifica altrimenti aumento solo le variabili. Non essendoci un comando diretto per effettuare questo cambio dobbiamo prima salvare l'elemento i-esimo in una variabile temporanea , sostituire l'elemento appena salvato con quello successivo (j-esimo) e poi sostituire l'elemento nella posizione j-esima con quello salvato nella variabile temporanea. L'operazione di sostituzione sovrascrive i dati da qui la necessità di salvare uno dei due numeri prima del cambio, naturalmente questo è uno dei modi utilizzabili e mi farebbe piacere vedere anche la vostra strategia.
Dalla simulazione possiamo vedere due cose importanti: 1) alla fine del primo passaggio il numero più grande è arrivato all'estremità destra 2) per 4 elementi abbiamo bisogno di 3 passaggi ( lunghezza della lista - 1 ).
Al prossimo passaggio la nostra lista però sarà più piccola perché escludiamo gli elementi già posizionati da qui lunghezza della lista -1 - n. passaggio ( mi raccomando attenzione a concatenare le sottrazioni con i blocchi di scratch ) .
Finito il primo passaggio andremo a incrementare la variabile numero di passaggi e impostiamo al valore inziale i e j per scorrere nuovamente la lista, questo ciclo esterno dovrà essere ripetuto lunghezza di lista -1 volte sempre perché lavorando con le coppie avremo sempre un'operazione in meno rispetto al totale elementi presenti.
Cosa ne pensate? Non è semplicissimo?
Per fare qualche prova ho anche realizzato un piccolo codice per popolare velocemente la lista di numeri da ordinare, se avete problemi scrivete pure nei commenti.
In questo caso ho impostato un massimo di 10 elementi da poter creare in un range di 50 ma con una piccola modifica può diventare molto interessante.
Compiti per casa 😂
Imposta il codice affinché si possa chiedere quanti elementi si vogliono introdurre nella lista. Buon divertimento e prossimamente vedremo come realizzare la stessa cosa con AppInventor.
PROGETTO SCRATCH
Link al progetto QUI
Commenti
Posta un commento