Bubble sort

Bubble sort

( AppInventor style )

Oggi vedremo come realizzare un codice per ordinare una lista di elementi casuali da noi creata. Visto che questo progetto è la continuazione del Bubble sort fatto con Scratch ( qui il post ) e che AppInventor presuppone di base qualche conoscenza in più andremo un po' più spediti rimandandovi naturalmente ai commenti per eventuali chiarimenti. La parte grafica come sempre la lascio al vostro gusto , io ho inserito due button per generare e ordinare la lista di numeri, una label per visualizzare tutti i numeri e un componente notifier per gestire eventuali notifiche e la scelta della quantità di numeri da generare. Se non sbaglio questa funzionalità era stata assegnata come compiti a casa per il progetto con Scratch, avete fatto i compiti ? 😂  

                    

Qui possiamo vedere un'anteprima di quello che andremo a creare, passiamo al codice e questa volta vedremo solo i blocchi utilizzati per creare la lista e ordinarla mentre tutto il resto della personalizzazione e l'introduzione nel progetto generale lo lascerò come compiti per casa 😝

Vediamo come creare una lista di numeri casuali e chiedere l'inserimento del numero massimo di elementi che si vogliono creare, ci servirà quindi una variabile lista che chiameremo lista_numeri (che fantasia 😂) e naturalmente il componente per le notifiche. Quando clicchiamo sul pulsante per creare la lista la prima cosa che facciamo è cancellare la lista di numeri, e voi vi chiederete perché se l'abbiamo appena creata vuota? Ottima domanda, torna a studiare 😅 Perché ogni volta che premiamo il pulsante dobbiamo pulire la lista che riceverà nuovi valori , mentre la creazione nell'initialize ha valore solo all'inizio della nostra app proprio per inizializzare il suo valore. Con lo stesso criterio andiamo a cancellare anche la label con tutti i numeri e facciamo partire la nostra notifica che chiederà quanti numeri vogliamo far creare al nostro appinventor. Nel mio caso ho impostato il messaggio non cancellabile non per cattiveria ma perché quella richiesta è un'informazione necessaria per continuare il progetto, questi dati saranno poi gestiti da noi grazie al blocco collegato alla notifica when notifier AfterTextInput dove andremo ad inserire il blocchi per creare la lista e anche tutti gli altri che serviranno per controllare ed evitare eventuali errori. Nel file .aia che posterò potrete vedere le scelte che ho adottato io.  Nel caso volessimo utilizzarlo sciolto da altre procedure

 

abbiamo bisogno di creare anche una variabile lunghezza_lista ed ho introdotto anche un'altra tipologia di variabile, quella locale, che ha valore e funziona solo all'interno del blocco a forma di c con cui impostiamo la variabile, sarà il nostro numero. Il blocco for each ormai è diventato il nostro più caro amico e in questo caso porta con se anche un'altra variabile lunghezza un po' particolare perché, oltre a valere solo all'interno della sua C , ci permette di impostare il suo range di utilizzo (che abbiamo impostato da 1 al valore della variabile lunghezza_lista , per capirci quella che per i compiti a casa dovrete far scegliere a chi usa l'app , quindi cambierà ad ogni utilizzo) e lo step con cui cambiare. Es. mettiamo il caso che abbiamo scelto di generare 10 numeri ( lunghezza_lista=10 ) il nostro for each farà in automatico 10 giri ed ad ogni giro cambierà il valore di lunghezza passandolo al codice al suo interno. Primo giro lunghezza=1 ed esegue il codice, secondo giro lunghezza=2 ed esegue il codice etc. Se lo step fosse stato impostato su 2 avremmo avuto lunghezza=1, lunghezza=3, lunghezza=5 etc. Adesso che abbiamo creato una procedura che ci permette di mandare in esecuzione un codice per 10 volte vediamo che codice eseguire e sarà quello per generare dei numeri random da inserire nella lista_numeri senza creare dei doppioni, non è essenziale in questo caso ma può risultare utile in altre occasioni. Impostiamo quindi una variabile locale e mi porto avanti con i passaggi da effettuare impostandola già come un numero random tra 1 e 100 (scelta personale) , una volta generato andiamo a controllare se è un doppione usando il blocco while test ... do. Gli stiamo dicendo di controllare se numero (che abbiamo appena generato) è presente nella lista lista_numeri e se questa informazione è vera e per tutto il tempo in cui lo sarà (tradotto mentre testi che il numero è nella lista) dovrà fare do qualcosa , nel nostro caso generare un altro numero casuale tra 1 e 100. Continuerà a farlo fino a quando non estrae un numero non presente nella lista. Solo quando il numero sarà corretto uscirà da questo giro infernale per andare ad aggiungere il numero alla lista lista_numeri. Ecco che abbiamo la nostra lista riempita di numeri casuali senza doppioni. Adesso tocca ordinarla però!

Anche qui lascio a voi come esercizio l'inserimento nel modo corretto del codice e vi rimando al file per vedere come lo ho introdotto io.

La prima cosa che salta all'occhio e che abbiamo due cicli annidati (fico eh 😂) , semplicemente uno dentro l'altro, quello di dentro fa il suo corso e quando ha finito viene ricatapultato in azione da quello più esterno. Partiamo dal cuore. Ci ricordiamo che il funzionamento dell'algoritmo consiste nel confrontare due numeri adiacenti (vicini) e se il primo dei due e maggiore del secondo lo scavalca prendendo il suo posto , lo supera spostandosi verso la fine della lista oppure immaginandoli in linea andrà verso destra. Alla fine di ogni giro (ciclo interno) saremo sicuri che il numero più grande arriverà in fondo alla lista o meglio nella posizione più estrema non già occupata. Questo significa che l'algoritmo non controllerà nuovamente i numeri già spinti e posizionati all'estremità , ottimizzando i tempi. Per questo motivo il ciclo interno dovrà avere una variabile che tiene conto del giro che sta facendo così da fermarsi nel momento esatto, l'abbiamo chiamata passaggi e sta ad indicare quante volte abbiamo controllato la lista di numeri e aumenterà ad ogni giro. Andando a sottrarre questo valore ad ogni passaggio potremo dire ad appinventor di fermarsi prima e non verificare tutti i numeri. Appena iniziamo passaggi=0 (il valore ce lo fornisce il ciclo più esterno) infatti dovremo controllare tutti i numeri della nostra lista, ma se controlliamo bene  il valore massimo a cui può arrivare il ciclo interno vediamo che è impostato come lunghezza della lista -1 infatti lavorando con confronti di coppie di numeri ci basterà  un giro in meno per verificare tutti numeri. Se abbiamo 10 numeri avremo bisogno di 9 verifiche, 9 confronti (n-1 volte). Quindi appena azioniamo il nostro codice il ciclo esterno passa come valore zero e quello interno farà 10-1-0 confronti quindi 9 eseguendo ogni volta il codice che ha al suo interno che porterà il numero più grande della lista all'eterno. Esaurito il ciclo interno si attiva nuovamente quello esterno ma questa volta passaggi=1 (cambia ad ogni giro e aumenta a step di 1) per cui questa volta il ciclo interno farà 10-1-1 volte il codice al suo interno , 8 verifiche intuendo quindi che non andremo a toccare l'ultimo numero già posizionato e ne porteremo un altro che sarà sicuramente il più grande rimasto ma più piccolo di quello già posizionato. Boom , riparte il ciclo esterno inviando passaggi=2 e questa volta il ciclo interno eseguirà 10-1-2 volta il suo codice , 7 verifiche e così andrà a scalare. Capite bene che collegando il codice alla variabile lunghezza_lista che facciamo inserire all'utente, noi non dovremo riscrivere un nuovo codice perché si modificherà all'occorrenza. Anche il ciclo esterno possiamo notare che proporrà n-1 passaggi sempre per lo stesso ragionamento di prima delle coppie , con la particolarità di partire da zero e abbiamo visto perché. Dopo aver giocato con i giri vediamo i blocchetti che lavorano veramente , visto che il ciclo interno porta con se una variabile numerica che aumenta gradualmente ed è già dimensionata con quello che controlliamo la useremo anche per muoverci all'interno della lista dove verificheremo e sposteremo i nostri numeri. Il nostro giro interno parte sempre da 1 infatti inizieremo con controllare il primo numero della lista e il suo vicino di banco quindi un posto dopo , infatti la condizione imposta nell' if dice controlla se il numero 1 (number) della lista è maggiore nel numero 1+1 (number+1) quindi quello vicino, se è vero spostali. Io ho trovato questo metodo voi potrete magari usarne un altro. Inserisci nella lista_numeri nella posizione number+1 (sarebbe quella del vicino di banco) che cosa? (item) l'elemento che sta nella posizione number . Questa operazione mi assicura che l'elemento che ho selezionato, sarebbe quello più grande dei due, prende proprio la posizione del più piccolo e riposiziona tutti gli altri numeri senza modificare il loro ordine ma mi genera un doppione per cui andrò in seguito a cancellare il numero originale (che sta ancora nella posizione number visto che sono slittati solo i numeri dopo) . Risultato finale il numero più grande ha saltato il più piccolino sorpassandolo , adesso il nostro number cambierà di valore e se prima abbiamo verificato il numero nella posizione 1 e 1+1 adesso controlleremo 2 e 2+1 , finito il mio controllo il ciclo interno si esaurisce e quello esterno da la carica per un altro passaggio.

Ottimo lavoro, siete riusciti ad ordinare la vostra lista di numeri? Ora non vi resta che portarla a video magari facendola vedere in una label oppure in una .....

Magari lo vedremo alla prossima puntata 😅 vi lascio il link per scaricare il progetto in formato .aia cosi da vedere tutto il mio codice 👉 QUI ma spero non vi serva.

Alla prossima