Altraidea-Cuneo.it periodico on line di informazione e di cultura

Algoritmi [3] – il calcolatore serve anzitutto a tenere in ordine i dati

di Piero Giuseppe Goletto

I francesi, che chiamano il calcolatore ordinateur, hanno capito una cosa fondamentale: la gran partedell’utilizzo degli elaboratori, nel mondo, è per tenere in ordine dati, cosa che implica il loro ordinamento.

Esempio classico: è molto agevole trovare le parole in un dizionario visto che sono riportate in ordine alfabetico. Il problema dell’ordinamento quindi consiste nel disporre in ordine una sequenza di elementi secondo un criterio uniforme. Nel caso del vocabolario questo si chiama “ordinamento lessicografico”: “abaco” viene prima di “abigeato” e questo precede “mantello”; la parola “zuzzurellone” risulta l’ultima o fra le ultime di tutto il dizionario. In termini matematici “ordinare” un insieme X significa trovare una permutazione degli elementi x 1 , x 2 , x 3 , x 4 , …. x n tale che si abbia x 1 ≤ x 2 ≤ x 3 ≤ x 4 ≤ …. ≤ x n . Si tenga conto che a fronte di due elementi di pari valore (esempio x 3 = x 4 ) non ha alcuna importanza il valore che compare per primo. Nella realtà concreta della programmazione, occorre distinguere il caso in cui l’ordinamento venga effettuato in memoria dal caso in cui questa stessa operazione avvenga su disco. Poniamo il caso che l’ordinamento avvenga in memoria: il caso più semplice di tutti è dover ordinare un insieme di numeri interi. Questo insieme è memorizzato in un array (sarebbe un vettore). Un modo per effettuare tale ordinamento è cercare all’interno di tale vettore il valore minimo e portarlo in prima posizione; scegliere il minimo tra gli elementi rimanenti, portarlo in seconda posizione e così via. Il valore presente in ciascuna posizione viene scambiato con il minimo così trovato. Un metodo simile consiste nel predisporre un array vuoto dentro il quale inserire i “minimi” via via individuati. L’array vuoto è ordinato, per costruzione, perché si sono inseriti sempre e solo i valori minimi reperiti. Il controllo che permette di determinare il valore minimo consiste nello scorrere l’array e tenere traccia del valore più basso tra il minimo trovato e il valore dell’elemento corrente. Fin qui esempi che vanno bene per spiegare a scuola cos’è l’ordinamento. Un algoritmo che è concretamente usato nella pratica si chiama bubble sort perché funziona un po’ come le bollicine delle bibite gassate.

L’algoritmo esamina le coppie di elementi (x 1 con x 2 ; x 2 con x 3 e così via). Poiché vale la relazione x 1 ≤ x 2 , se trova x 1 ≥ x 2 li scambia di posto; in caso contrario li lascia come li ha trovati. L’algoritmo che viene reso disponibile nelle librerie dei linguaggi di programmazione evoluti è però il quicksort: ordinamento rapido; si tratta dell’algoritmo più veloce. Si prende l’array, si individua una porzione e all’interno di questa un valore pivot, si suddivide la porzione in tre parti a seconda che i valori siano minori, uguali o maggiori al pivot e si effettuano scambi in modo tale da portare i valori più bassi verso l’inizio della porzione di array e i valori più alti in coda all’array stesso.

Mostly Cloudy

24°C

Cuneo

Mostly Cloudy

Humidity: 67%

Wind: 11.27 km/h

  • 17 Aug 2018

    Thunderstorms 25°C 17°C

  • 18 Aug 2018

    Scattered Showers 26°C 16°C

Partly Cloudy

28°C

Nizza

Partly Cloudy

Humidity: 57%

Wind: 11.27 km/h

  • 17 Aug 2018

    Thunderstorms 28°C 23°C

  • 18 Aug 2018

    Scattered Showers 28°C 22°C