Algoritmi in pillole: bubble sort

Animazione dell'algoritmo di Bubble sort da wikipedia

Animazione dell'algoritmo di ordinamento bubble sort da wikipedia

L'algoritmo controlla ogni coppia di elementi adiacenti  e li scambia se non sono ordinati. L'algoritmo procede così fino a quando non ci sono più scambi da fare. 

pseudocodice:

"per i che varia da 0 a N-1
   per j che varia da N-1 a i+1
      se l'elemento j è minore dell'elemento j-1
        allora scambia l'elemento j con l'elemento j-1"

Codice:

void bubblesort(int v[], int n) {
  int i=0,j,temp;
  int scambio = FALSE;
  do {
    scambio=FALSE;
    for (j=n-1;j>i;j--)
      if (v[j]<v[j-1]) {
        temp=v[j];
        v[j]=v[j-1];
        v[j-1]=temp;
        scambio=TRUE;
      }
      i=i+1;
    } while(i<n-1 && scambio);
}

La complessità computazionale asintotica è O(n^2).
Caso peggiore: array ordinato in senso inverso - T. esec. prop. a n^2
Caso migliore: array già ordinato                     - T. esec. prop. a n

Simple linked list o liste concatenate semplici (parte III): stampiamo le liste

Terzo post sull'argomento liste semplici collegate o linked lists. Spero non siate stanchi:)
Forse, se vedessimo insieme qualche funzione di servizio si potrebbe provare a superare la stanchezza?
Io ci provo.
Nei due precedenti post, qui e qui, abbiamo creato e modificato la nostra lista. Ma, come facciamo a vedere quello che c'è dentro la lista? Ovviamente con una funzione che ci stampa a schermo la lista.
Vediamo come:

Algoritmi in pillole C: ordinamento con insertion sort

Animazione dell'algoritmo Insertion sort da Wikipedia

Se l'ordine desiderato è quello crescente,  l'algoritmo parte dall'ipotesi che l'array da ordinare sia composto da un primo elemento ordinato e una seconda parte "disordinata". Esamina quindi il primo elemento disordinato confrontandolo con tutti gli elementi "ordinati". Ad ogni confronto, se l'elemento disordinato è minore di quello ordinato si "inserisce", da qui il nome dell'algoritmo, l'elemento disordinato al posto di quello ordinato, scambiandoli di posto. Al termine di questa fase si avrà una parte ordinata composta da due elementi e una parte disordinata composta da N-2 elementi. L'algoritmo continua ad esaminare la parte disordinata fino alla fine dell'array.

Pseudocodice:

"per i che varia da 1 a N
   per j che varia da i a 0
     se l'elemento j è minore dell'elemento i allora
       scambia l'elemento i con l'elemento j"

Codice:

void insertSort(int * ar, int  n)
{
  int  i, j, temp;
  for (i = 1; i < n; t++){
    j = i;
    while( (j > 0) && (ar[j] < ar[j - 1] )) {
      temp = ar[j];
      ar[j] = ar[j - 1];
      ar[j - 1] = temp;
      j--;
    }
  }
}

La complessità computazionale asintotica è O(n^2).

Caso peggiore: array ordinato in senso inverso - T. esec. prop. a n^2
Caso migliore: array già ordinato                      - T. esec. prop. a n

Piccolo tutorial sul linguaggio C - Gli operatori aritmetici e logici

Operatori aritmetici

Nel nostro termostato avremo bisogno di fare calcoli! Vediamo cosa ci offre il C a questo scopo. Il linguaggio C comprende i consueti operatori:
Operatori binari

+ Somma;
- Sottrazione;
/ Divisione;
* Moltiplicazione;
% Resto (mod);

Operatori unari (prefissi e suffissi)

++ incremento di 1
-- decremento di 1

In un precedente post, avevamo già visto quali possono essere i pericoli derivanti dall'uso non attento dei semplici operatori aritmetici binari in presenza di variabili e costanti di tipi diversi dal tipo del risultato. Per riassumere, il segno di diviso tra due interi è interpretato come divisione tra interi. Ovvero, 1/3 è uguale a 0! Anche gli operatori unari di incremento/decremento possono presentare dei comportamenti, a prima vista, bizzarri se non se ne conosce bene il funzionamento.  Commentiamo insieme un esempio:

i=1;     //istr. 1
j=ì++;  //istr. 2
k=++ì; //istr. 3

Secondo voi, dopo il precedente blocco di istruzioni, quanto vale j? Chi ha detto 2?Nessuno  dice 1? La risposta esatta è 1! Infatti, l'operatore suffisso viene applicato alla fine della valutazione dell'espressione nella quale si trova. Se il gioco è chiaro, la prossima domanda dovrebbe essere facile: quanto vale k? Bravi! Avete risposto bene. Il valore assunto da k è proprio 3, perché dopo l'istruzione 2 i vale 2 e quando viene valutata l'istruzione 3, i viene prima incrementato di 1, quindi vale 3, e poi usato nell'espressione a destra del segno uguale.

Operatori relazionali

Abbiamo già detto che il linguaggio C non prevede un tipo booleano primitivo? Se non lo abbiamo detto, lo diciamo qui :). In C, 0 (zero) corrisponde al valore booleano False, qualunque altro valore è True.
Gli operatori relazionali operano su valori interi o decimali e restituiscono il valore 0 oppure 1.

• == Uguale a
• != Non uguale a, Diverso da
• > Maggiore di
• < Minore di
• >= Maggiore o uguale a
• <= Minore o uguale a

Attenzione: per testare l'uguaglianza si usa l'operatore == e non l'operatore =, che è invece l'operatore di assegnamento.
Commentiamo insieme un esempio per capire cosa può succedere se usiamo l'operatore sbagliato.
Immaginano di voler disporre di una variabile di nome manuale che ci dica se è stat impostata la modalità manuale del termostato, vi ricordo che le specifiche del termostato sono in questo post e che la modalità manuale si seleziona premendo il tasto 'a'. Quindi, da qualche parte nel nostro programmino potremmo scrivere:

manuale = (comandotastiera='a'); // istr. 1
...
if (manuale) fai_qualcosa();          // istr. 2

Purtroppo, invece di scrivere comandotastiera=='a' abbiamos scritto comandotastiera='a', con il risultato di assegnare alla variabile manuale il risultato dell'espressione comandotastiera='a' che è esattamente 'a', ovvero il codice numerico del carattere 'a' che è pari a 97. Poiché 97 è maggiore di 0, il test sulla variabile manuale è sempre verificato e quindi il nostro termostato sarebbe sempre in modalità manuale acceso.
Si noti che l'istruzione 1, benché non faccia ciò che volevamo che facesse, è perfettamente legittima e quindi il compilatore non segnala alcun errore!
Visto cosa può succedere scrivendo = invece di ==?

Operatori logici

Lo abbiamo già detto: 0 è False, qualunque altro valore è vero!
Gli operatori logici sono

• ! not, negazione Booleana (unario)
• && and Booleano 
• || or Booleano 

Operatori logici bit a bit

• ~ Negazione bit a bit (unario) – cambia tutti gli 0 in 1 e gli 1 in 0 
• & esegue l'And dei bit dell'operando di sinistra con i bit dell'operando di destra
• | esegue l'Ordei bit dell'operando di sinistra con i bit dell'operando di destra
• ^ esegue l'Or esclusivo dei bit dell'operando di sinistra con i bit dell'operando di destra
• >> Shifta a destra di un numero di bit pari all'operando a destra (=divisione per potenze di 2)
• <<  Shifta a sinistradi un numero di bit pari all'operando a destra (=moltiplicazione per potenze di 2)

Anche qui, attenzione a non confondere gli operatori logici con quelli bit a bit, il compilatore non vi aiuterà nel caso di errori!

Operatori di assegnamento 

Oltre al classico operatore di assegnamento il linguaggio C prevede le seguenti "scorciatoie":per effettuare operazioni di assegnamento e modifica di una variabile con un solo riferimento alla variabile stessa. La sintassi è la seguente:

var op= espr;

dove op può essere uno qualunque tra gli operatori: + - * / % & | ^ << >>.  Il significato è il seguente: assegna a var il risultato di var op espressione. Vediamo con un esempio a cosa servono. L'istruzione 
i  =  i * 10;
può essere riscritta con l'operatore di assegnamento è equivalente a
ì *=10;
Gli ideatori del C  hanno pensato che questo tipo di operatori avrebbe aumentato la leggibilità dei programmi  introducendo questo modo di rappresentare di modifica ad una variabile basata su se stessa.
Inoltre, l'uso di questi operatori può contribuire alla scrittura di codice più efficiente. Il compilatore quando incontra un operatore di assegnamento può implementare l'operatore con un istruzioni più veloci che nel caso di assegnamento semplice.

Precedenze degli operatori del linguaggio C

La seguente tavola delle precedenze degli operatori in C dovrebbe essere sempre a portata di mano. Soprattutto quando si sta imparando il linguaggio di programmazione. Ma, anche i più esperti potranno trarre beneficio dall'avere riassunti in una unica tabella tutti gli operatori con le loro precedenze e associatività (= ordine di precedenza che viene seguito quando si trovano più operatori di uguale precedenza nella stessa espressione).

Operatore	Descrizione	Associatività
( ) [ ] . -> ++ --	Parentesi (chiamata a funzione) (vedi Nota 1) Parentesi quadre (array) selezione di membri di oggetti dal nome come sopra, ma dal puntatore incrementi/decrementi postfissi (vedi Nota 2)	da sx a dx
++ -- + - ! ~ (type) * & sizeof	incrementi/decrementi prefissi più/meno unari negazione logia/complemento bit a bit cast (conversione di tipi) deferenza indirizzo (di operandi) dimensioni in byte (dipendente dalla piattaforma)	da dx a sx
*  /  %	moltiplicazione/divisione/modulo	da sx a dx
+  -	Aaddizione/sottrazione	da sx a dx
<<  >>	shift a sinistra/destra bit a bit	da sx a dx
<  <= >  >=	operatori relazionali minore di/minore o uguale a operatori relazionali maggiore di/maggiore o uguale a	da sx a dx
==  !=	operatore relazionale uguale a/ non uguale a	da sx a dx
&	AND bit a bit	da sx a dx
^	OR esclusivo bit a bit	da sx a dx
|	OR bit a bit	da sx a dx
&&	AND logico	da sx a dx
| |	OR logico	da sx a dx
? :	condizionale ternario	da dx a sx
= +=  -= *=  /= %=  &= ^=  |= <<=  >>=	assegnazione assegnazione con addizione/sottrazione assegnazione con moltiplicazione/divisione assegnazione con modulo/AND bit a bit assegnazione con OR esclusivo bit a bit/Or  bit a bit assegnazione con shift a sinistra/shift a destra bit abit	da dx a sx
,	virgola (separatore di espressioni)	da sx a dx

Nota 1:Le parentesi sono usate anche per raggruppare sottoespressioni per forzare le precedenze. Nel caso di parentesi nidificate, l'ordine di precedenza è dalla più interna alla più esterna.

Note 2:Gli operatori di incremento postfissi hanno alta precedenza, ma l'incremento7decremnto reale è rimandato fino alla fine della valutazione dell'espressione. Ad esempio nell'esecuzione di a=3*i++, se i valeva 1 prima di questa istruzione,  a varrà 3 e i varrà 2. Cioè i è incrementato al termine dell'esecuzione dell'istruzione.

Simple linked list o liste concatenate semplici (parte II)

Se chiedete a 10 programmatori diversi : "Quali funzioni servono per gestire le liste?", probabilmente otterreste 10 risposte diverse, perché dipende dall'applicazione e dalle strutture dati complesse che si intendono implementare con le liste. Quindi, senza la pretesa di essere esaustivi, analizziamo insieme alcune funzioni di "base" per la creazione, modifica, stampa ed eliminazione di liste. In particolare, in questa piccola serie di post sulle liste collegate semplici, vedremo le seguenti funzioni:


void push(int pl, nodeP *sP, nodeP *eP);
void pop(int *pl,  nodeP *sP, nodeP *eP);
void delnode(int pl, int global, nodeP *sP, nodeP *eP);
void genlist(int N, nodeP* sP, nodeP* eP);
void destroy(nodeP *sp);
void printlistv(nodeP head);
void printlisto(nodeP head);

Come si misura ill tempo di esecuzione di un blocco di codice C?

Misurare le performance di un frammento codice o di una funzione può essere utile per valutare le prestazioni (benchmarcking) del proprio codice o per decidere tra diversi approcci per la soluzione di un certo problema qual'è il più veloce. In un precedente post, abbiamo visto come misurare il tempo di esecuzione di un eseguibile utilizzando il comando Unix Time, disponibile anche su Windows in CigWin. Invece, per misurare la velocità di esecuzione di un frammento di codice all'interno di un programma scritto in C si può usare la funzione clock(), il cui prototipo si trova in <time.h>.
La funzione clock() restituisce il numero di cicli di clock dall'ultima chiamata della funzione. In <time.h> c'è anche una costante chiamata CLOCK_PER_SEC che fornisce il numero di clock per secondo per la piattaforma hardware e software che si sta usando.

Simple linked list o liste concatenate semplici (parte I)

Una lista concatenata semplice, o linked list e per brevità da qui in poi lista, è una struttura dati che consente la memorizzazione di informazioni in elementi, detti anche nodi, non contigui collegati sequenzialmente  da un legame .

Lista concatenata semplice di 3 interi

Algoritmi in pillole C: ordinamento con selection sort

Selection sort animata da wikipedia

Se l'ordine desiderato è quello crescente,  l'algoritmo "seleziona" il valore più piccolo dell‟array di n elementi e lo scambia con quello al primo posto. Successivamente, "seleziona" il più piccolo tra gli n-1 elementi rimasti e lo scambia con quello al secondo posto, e così via fino a che non rimane un solo elemento, l'ultimo e il più grande. 

pseudocodice:

"per i che varia da 1 a  N   per j che varia da i+1 a N       se l'elemento j è minore dell'elemento i allora          scambia i con j"

Codice:

void selectionsort(int v[], int n){
 int i,j,min,temp;
 for (i=0;i<n-1;i++) {
   min=i;
   for (j=i+1;j<n;j++)
     if (v[j]<v[min]) min=j;
   temp=v[i];
   v[i]=v[min];
   v[min]=temp;
 }
}

La complessità computazionale asintotica è O(n^2).
Caso peggiore: array ordinato in senso inverso - T. esec. prop. a n^2
Caso migliore: array già ordinato                     - T. esec. prop. a n^2

Piccolo tutorial sul linguaggio C - le conversioni di tipo

Le specifiche del progetto del nostro termostato indicano che la funzione che dialoga con il sensore esterno fornisce la temperatura nel seguente modo:

Per ottenere la temperatura ambientale si dovrà usare la funzione dammitemperatura() che restituisce un valore intero compreso tra  -1000  e +1000 per valori di temperatura compresi tra -50 °C e +50 °C. il prototipo della funzione dammitemperatura() è il seguente:

• int dammitemperatura();

Piccolo tutorial sul linguaggio C - i puntatori in C

Uno dei meccanismi più potenti e, allo stesso tempo, più insidiosi del C è l'uso dei puntatori. Un puntatore è una variabile, quindi un contenitore di dati, che, invece che contenere il dato di interesse, contiene il valore numerico dell'indirizzo di memoria del dato di interesse. Per fare un po di chiarezza su questo argomento, commentiamo insieme il programma di esempio riportato qui a sinistra. Come abbiamo già visto in un post precedente, utilizziamo anche una rappresentazione grafica stilizzata della memoria fisica del computer riportata nella figura qui sotto.

Piccolo tutorial sul linguaggio C - le variabili in C

Quando dichiariamo una variabile in C, il compilatore riserva in memoria, in una struttura dati denominata stack, il numero di bytes necessari per memorizzare il tipo di dato della variabile. Ad esempio, nella figura qui sotto, possiamo vedere cosa succede alla memoria fisica del computer quando eseguiamo il programma C riportato nella figura a sinistra.

Piccolo tutorial sul linguaggio C - tipi di dato primitivi

Questo è il primo di una breve serie di post dedicati ad un piccolo tutorial sul linguaggio C. Durante questo breve viaggio nel C, come pretesto per introdurre i costrutti del linguaggio stesso, realizzeremo un semplice termostato ambiente in C.

 Le specifiche del progetto sono le seguenti: 

Il mio ritratto al museo della scienza di Londra :)