Algoritmica – esercizio di logica sugli array

Quanto è importante conoscere bene un linguaggio di programmazione?
Sicuramente molto.  Ma è sufficiente per essere un buon programmatore? Certamente no. La vera bellezza (e utilità) della programmazione non consiste nel creare finestre dal design accattivante o alla destrezza nello sfruttare i ridondanti pulsanti di un ambiente di sviluppo, bensì nella soddisfazione che si prova a trovare una soluzione creativa ad un quesito ostico, soprattutto se ci è costato nottate di lavoro. È l’algoritmo il reale fulcro della programmazione.
In questo articolo proporrò un classico dell’algoritmica, ossia, l’ordinamento di un array. Studieremo insieme 3 tecniche molto note. Premetto che le mie sono proposte tratte da classici dell’algoritmica che non voglio passare come mie invenzioni.

Un primo algoritmo (Minimo)

Sappiamo tutti cosa sia un array.
Per coloro che si stanno affacciando da poco tempo al mondo della programmazione, un array è una variabile strutturata composta da un certo numero di celle ognuna delle quali può contenere un valore e alle quali si accede tramite un indice che ne identifica la posizione all'interno dell’array stesso.

12 65 -98 1456 0 38 67 81

A seconda del linguaggio di programmazione utilizzato per sviluppare l’algoritmo, gli array vengono definiti e gestiti con tecniche differenti.
Gli algoritmi del presente articolo sono sviluppati in C++, linguaggio principe nel mondo del software e che si presta benissimo allo scopo.
Utilizzando C++ l’array visualizzato sopra è composto da 8 celle con indice che va da 0 a 7, pertanto la prima cella contenente il valore numerico 12 ha indice 0, la cella di valore 38 ha indice 5 e l’ultimo elemento ha indice 7.
L’array dell'esempio contiene numeri interi e in C++ lo possiamo definire in questo modo:

int tab[8];

Bene, veniamo alla prima tecnica che non avendo un nome specifico ho chiamato Minimo.
Il nostro obiettivo, ricordo, è ordinare un array in ordine crescente.
Per ottenere lo scopo scorriamo tutto l’array per cercare l’elemento di valore più basso e una volta trovato lo inseriamo nella sua prima cella; ovviamente il valore che si trova nella prima cella non deve essere perso e per comodità lo spostiamo nel posto in cui si trovava il valore minimo.
Sempre considerando l’array:

12 65 -98 1456 0 38 67 81

l’elemento di valore più basso è -98 ed è collocato nella cella di indice 2; dopo un primo giro dell’algoritmo l’elemento -98 si deve trovare nella prima cella (la cella 0) e il contenuto della prima cella va spostato al posto del valore rintracciato.

-98 65 12 1456 0 38 67 81

Ripetiamo il ragionamento; questa volta però non consideriamo tutto l’array ma solo la parte che inizia dalla cella di indice 1 quindi si ragiona su un sotto array composto dalle sole 7 celle rimanenti:

65 -98 1456 0 38 67 81

Cercando il valore minimo della parte restante e inserendolo nella sua prima cella (che corrisponde alla cella di indice 1 dell'array originale), abbiamo in realtà trovato il secondo valore più basso dell’array che risulta, alla fine del secondo giro, parzialmente ordinato:

-98 0 12 1456 65 38 67 81

Il terzo giro considera l’array solo a partire dalla cella 2 e in questo caso il valore più basso è già collocato al posto giusto ma, importante ai fini della valutazione della bontà dell'algoritmo, l'array viene comunque percorso dalla cella 2 alla 7:

-98 0 12 1456 65 38 67 81

La quarta iterazione considera solo le celle 3, 4, 5, 6 e 7 e recupera il valore minimo 38 posizionandolo nella cella di indice 3:

-98 0 12 38 65 1456 67 81

Siamo arrivati alla cella numero 4: il valore più basso tra 65, 1456, 67 e 81 si trova nella cella di indice 4, quindi l'array non subisce modifiche anche se i confronti sulle celle restanti avvengono lo stesso:

-98 0 12 38 65 1456 67 81

Un altro giro che inizia dalla cella di indice 5 recupera il valore minimo 67 che viene scambiato con 1456 appartenente proprio alla cella numero 5:

-98 0 12 38 65 67 1456 81

Un ultimo confronto tra le due celle rimanenti individua 81 come valore minimo delle celle 6 e 7 (rispettivamente la settima e l'ottava). [...]

ATTENZIONE: quello che hai appena letto è solo un estratto, l'Articolo Tecnico completo è composto da ben 2711 parole ed è riservato agli abbonati PLATINUM. Con l'Abbonamento avrai anche accesso a tutti gli altri Articoli Tecnici MAKER e PLATINUM e potrai fare il download (PDF) di tutti gli EOS-Book, Firmware e degli speciali MONOTEMATICI. ABBONATI ORA, è semplice e sicuro.

Abbonati alle riviste di elettronica

6 Commenti

  1. Maurizio Di Paolo Emilio Maurizio 22 marzo 2016
  2. epifas1 22 marzo 2016
  3. Dennis Zignin 7 luglio 2016

Scrivi un commento