Array, un primo algoritmo utile: il sorting
Ordinare sequenze in base a un criterio è di fondamentale importanza per tantissime applicazioni
Esistono tantissimi algoritmi di sorting , da usare a seconda delle diverse esigenze
Qui un video che ne mostra schematicamente nove:
VIDEO
Noi implementeremo il più lento di tutti!
Il bubblesort
I dati contenuti nell’array vengono ordinati dal più piccolo al più grande
L’algoritmo è O ( N 2 ) , cioè in media il tempo richiesto scala con il quadrato della dimensione dell’array
L’ordinamento si basa sul confronto tra elementi contigui nell’array
Il contenuto della casella di sinistra è maggiore di quello della casella di destra? → si invertono i valori
Supponiamo di voler riordinare il seguente array:
data[0]
data[1]
data[2]
data[3]
3
5
-2
1
Una prima iterazione
data[0]
data[1]
data[2]
data[3]
3
5
-2
1
Cominciamo a confrontare le coppie di elementi contigui, partendo dall’inizio
data[0] > data[1]
? No: non facciamo nulla
data[1] > data[2]
? Sì! Invertiamo i valori, l’array diventa
data[0]
data[1]
data[2]
data[3]
3
-2
5
1
data[2] > data[3]
? Sì! Invertiamo i valori, l’array diventa
data[0]
data[1]
data[2]
data[3]
3
-2
1
5
Alla fine della prima iterazione, l'ultimo elemento contiene il valore maggiore!
Traduciamo la prima iterazione in codice
Nel codice che segue
DIM_ARRAY
è la dimensione dell’array
data
contiene la sequenza da riordinare
temp
è una “variabile di appoggio” che serve per scambiare il contenuto di due caselle
for (j = 0 ; j < DIM_ARRAY - 1 ; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
for (j = 0 ; j < DIM_ARRAY - 1 ; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
for (j = 0 ; j < DIM_ARRAY - 1 ; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
for (j = 0 ; j < DIM_ARRAY - 1 ; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
data[0]
data[1]
data[2]
data[3]
3
5
-2
1
→
data[0]
data[1]
data[2]
data[3]
3
-2
1
5
Seconda iterazione
data[0]
data[1]
data[2]
data[3]
3
-2
1
5
Poiché l’ultimo elemento è il più grande, confrontiamo tutte le coppie tranne l’ultima
data[0] > data[1]
? Sì! Invertiamo i valori, l’array diventa
data[0]
data[1]
data[2]
data[3]
-2
3
1
5
data[1] > data[2]
? Sì! Invertiamo i valori, l’array diventa
data[0]
data[1]
data[2]
data[3]
-2
1
3
5
Traduciamo la seconda iterazione in codice
Simboli e variabili come per la prima interazione
for (j = 0 ; j < DIM_ARRAY - 1 - 1 ; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
data[0]
data[1]
data[2]
data[3]
3
-2
1
5
→
data[0]
data[1]
data[2]
data[3]
-2
1
3
5
L'array è ordinato! Sono servite 2 iterazioni, ma con N dati ne possono servire fino a N − 1 . Qual è il caso peggiore?
Un passo ulteriore: il codice per l’i
-esima iterazione
Se la variabile iter
contiene il numero dell’iterazione (partendo da 0), allora
for (j = 0 ; j < DIM_ARRAY - 1 - iter; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
Aggiungiamo il ciclo più esterno
for (iter = 0 ; iter < DIM_ARRAY - 1 ; iter++) {
for (j = 0 ; j < DIM_ARRAY - 1 - iter; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
}
Il ciclo più esterno viene eseguito DIM_ARRAY - 1
volte
Quello più interno è via via più breve più iter
è grande
Esempio: quando iter == DIM_ARRAY - 2
, DIM_ARRAY - 1 - iter == 1
, quindi il ciclo interno ha un’unica ripetizione!
Il codice completo
#include <stdio.h>
#define DIM_ARRAY 10
int main () {
double data[DIM_ARRAY], double temp;
int iter, j;
printf ("Inserire %d numeri: \n" , DIM_ARRAY);
for (j = 0 ; j < DIM_ARRAY; j++) {
scanf ("%lf" , &data[j]);
}
for (iter = 0 ; iter < DIM_ARRAY - 1 ; iter++) {
for (j = 0 ; j < DIM_ARRAY - 1 - iter; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
}
for (j = 0 ;j < DIM_ARRAY; j++) {
printf (".4%lf " , data[j]);
}
printf ("\n" );
return 0 ;
}
#include <stdio.h>
#define DIM_ARRAY 10
int main () {
double data[DIM_ARRAY], double temp;
int iter, j;
printf ("Inserire %d numeri: \n" , DIM_ARRAY);
for (j = 0 ; j < DIM_ARRAY; j++) {
scanf ("%lf" , &data[j]);
}
for (iter = 0 ; iter < DIM_ARRAY - 1 ; iter++) {
for (j = 0 ; j < DIM_ARRAY - 1 - iter; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
}
for (j = 0 ;j < DIM_ARRAY; j++) {
printf (".4%lf " , data[j]);
}
printf ("\n" );
return 0 ;
}
#include <stdio.h>
#define DIM_ARRAY 10
int main () {
double data[DIM_ARRAY], double temp;
int iter, j;
printf ("Inserire %d numeri: \n" , DIM_ARRAY);
for (j = 0 ; j < DIM_ARRAY; j++) {
scanf ("%lf" , &data[j]);
}
for (iter = 0 ; iter < DIM_ARRAY - 1 ; iter++) {
for (j = 0 ; j < DIM_ARRAY - 1 - iter; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
}
for (j = 0 ;j < DIM_ARRAY; j++) {
printf (".4%lf " , data[j]);
}
printf ("\n" );
return 0 ;
}
#include <stdio.h>
#define DIM_ARRAY 10
int main () {
double data[DIM_ARRAY], double temp;
int iter, j;
printf ("Inserire %d numeri: \n" , DIM_ARRAY);
for (j = 0 ; j < DIM_ARRAY; j++) {
scanf ("%lf" , &data[j]);
}
for (iter = 0 ; iter < DIM_ARRAY - 1 ; iter++) {
for (j = 0 ; j < DIM_ARRAY - 1 - iter; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
}
for (j = 0 ;j < DIM_ARRAY; j++) {
printf (".4%lf " , data[j]);
}
printf ("\n" );
return 0 ;
}
#include <stdio.h>
#define DIM_ARRAY 10
int main () {
double data[DIM_ARRAY], double temp;
int iter, j;
printf ("Inserire %d numeri: \n" , DIM_ARRAY);
for (j = 0 ; j < DIM_ARRAY; j++) {
scanf ("%lf" , &data[j]);
}
for (iter = 0 ; iter < DIM_ARRAY - 1 ; iter++) {
for (j = 0 ; j < DIM_ARRAY - 1 - iter; j++) {
if (data[j] > data[j + 1 ]) {
temp = data[j];
data[j] = data[j + 1 ];
data[j + 1 ] = temp;
}
}
}
for (j = 0 ;j < DIM_ARRAY; j++) {
printf (".4%lf " , data[j]);
}
printf ("\n" );
return 0 ;
}
$ ./es_bubblesort
Inserire 10 numeri:
2 5.1 -1.2 0 -6.4 2.6 5 1.9 9.5 -7.6
-7.6000 -6.4000 -1.2000 0.0000 1.9000 2.0000 2.6000 5.0000 5.1000 9.5000
$ ./es_bubblesort
Inserire 10 numeri:
2 5.1 -1.2 0 -6.4 2.6 5 1.9 9.5 -7.6
-7.6000 -6.4000 -1.2000 0.0000 1.9000 2.0000 2.6000 5.0000 5.1000 9.5000
Un altro algoritmo utile: ricerca binaria
Scorrere una sequenza per cercare un elemento particolare è O ( N ) (“ordine N ”)
La ricerca binaria cerca in maniera efficiente (O ( log 2 N ) ) un elemento in una sequenza ordinata
target
è il numero da trovare, middle
è l’elemento centrale della sequenza,
Se middle == target
la ricerca è finita, usciamo dal ciclo
Se middle > target
, target
si trova nella parte di sequenza a sx di middle
Se middle < target
, target
si trova nella parte di sequenza a dx di middle
Torniamo al passo 1, considerando la porzione di sequenza in cui sappiamo essere target
Diagramma di flusso della ricerca binaria
Una possibile implementazione
#include <stdio.h>
#define DIM_ARRAY 10
int main () {
int data[DIM_ARRAY];
int start = 0 , int end = DIM_ARRAY -1 ;
int middle, target, found = 0 ;
printf ("Inserire %d numeri ordinati dal più piccolo al più grande \n" , DIM_ARRAY);
for (i = 0 ; i < DIM_ARRAY; i++){
scanf ("%i" , &data[i]);
}
printf ("Inserire il numero da cercare:\n" );
scanf ("%d" , &target);
do {
middle = (start + end) / 2 ;
if (data[middle] == target) {
found = 1 ;
}
else if (data[middle] < target) {
start = middle + 1 ;
}
else {
end = middle - 1 ;
}
} while (!found && start <= end);
if (found) {
printf ("Elemento trovato alla posizione %d\n" , middle);
}
else {
printf ("Elemento non trovato :-(\n" );
}
return 0 ;
}
#include <stdio.h>
#define DIM_ARRAY 10
int main () {
int data[DIM_ARRAY];
int start = 0 , int end = DIM_ARRAY -1 ;
int middle, target, found = 0 ;
printf ("Inserire %d numeri ordinati dal più piccolo al più grande \n" , DIM_ARRAY);
for (i = 0 ; i < DIM_ARRAY; i++){
scanf ("%i" , &data[i]);
}
printf ("Inserire il numero da cercare:\n" );
scanf ("%d" , &target);
do {
middle = (start + end) / 2 ;
if (data[middle] == target) {
found = 1 ;
}
else if (data[middle] < target) {
start = middle + 1 ;
}
else {
end = middle - 1 ;
}
} while (!found && start <= end);
if (found) {
printf ("Elemento trovato alla posizione %d\n" , middle);
}
else {
printf ("Elemento non trovato :-(\n" );
}
return 0 ;
}
#include <stdio.h>
#define DIM_ARRAY 10
int main () {
int data[DIM_ARRAY];
int start = 0 , int end = DIM_ARRAY -1 ;
int middle, target, found = 0 ;
printf ("Inserire %d numeri ordinati dal più piccolo al più grande \n" , DIM_ARRAY);
for (i = 0 ; i < DIM_ARRAY; i++){
scanf ("%i" , &data[i]);
}
printf ("Inserire il numero da cercare:\n" );
scanf ("%d" , &target);
do {
middle = (start + end) / 2 ;
if (data[middle] == target) {
found = 1 ;
}
else if (data[middle] < target) {
start = middle + 1 ;
}
else {
end = middle - 1 ;
}
} while (!found && start <= end);
if (found) {
printf ("Elemento trovato alla posizione %d\n" , middle);
}
else {
printf ("Elemento non trovato :-(\n" );
}
return 0 ;
}
#include <stdio.h>
#define DIM_ARRAY 10
int main () {
int data[DIM_ARRAY];
int start = 0 , int end = DIM_ARRAY -1 ;
int middle, target, found = 0 ;
printf ("Inserire %d numeri ordinati dal più piccolo al più grande \n" , DIM_ARRAY);
for (i = 0 ; i < DIM_ARRAY; i++){
scanf ("%i" , &data[i]);
}
printf ("Inserire il numero da cercare:\n" );
scanf ("%d" , &target);
do {
middle = (start + end) / 2 ;
if (data[middle] == target) {
found = 1 ;
}
else if (data[middle] < target) {
start = middle + 1 ;
}
else {
end = middle - 1 ;
}
} while (!found && start <= end);
if (found) {
printf ("Elemento trovato alla posizione %d\n" , middle);
}
else {
printf ("Elemento non trovato :-(\n" );
}
return 0 ;
}
Generatori di numeri pseudocasuali
Esistono molti algoritmi che richiedono numeri casuali per essere eseguiti
Veri numeri casuali richiedono hardware apposito
Nella maggior parte dei casi è sufficiente utilizzare numeri pseudocasuali
Le sequenze sono solo apparentemente casuali
Il processo che le genera è interamente deterministico
Poiché il processo è deterministico, la stessa sequenza può essere generata più volte: utilissimo per testare algoritmi
La sequenza non è veramente casuale, e questo può dare problemi nelle applicazioni (ad es., la sequenza potrebbe ripetersi)
Generare numeri pseudocasuali in C
Un generatore pseudocasuale è un algoritmo che genera sequenze di numeri
Sequenze pseudocasuali approssimano le proprietà statistiche di vere sequenze casuali
La sequenza è completamente determinata dai parametri del generatore e da un valore iniziale: il seme
Stesso seme e stesso generatore → stessa sequenza
Le funzioni della libreria standard del C per generare numeri pseudocasuali sono definite in stdlib.h
Esistono due famiglie di funzioni: noi useremo sempre quelle che terminano con 48
:
srand48(long int seed)
usa seed
per inizializzare la sequenza
drand48()
restituisce un double
∈ [ 0 , 1 )
lrand48()
restituisce un long int
∈ [ 0 , 2 31 )
mrand48()
restituisce un long int
∈ [ − 2 31 , 2 31 )
Numeri pseudocasuali - un primo esempio
#include <stdlib.h>
#include <stdio.h>
int main () {
srand48(123456 );
double x = drand48();
double y = drand48();
printf ("Ecco due numeri pseudocasuali: %lf %lf\n" , x, y);
return 0 ;
}
#include <stdlib.h>
#include <stdio.h>
int main () {
srand48(123456 );
double x = drand48();
double y = drand48();
printf ("Ecco due numeri pseudocasuali: %lf %lf\n" , x, y);
return 0 ;
}
#include <stdlib.h>
#include <stdio.h>
int main () {
srand48(123456 );
double x = drand48();
double y = drand48();
printf ("Ecco due numeri pseudocasuali: %lf %lf\n" , x, y);
return 0 ;
}
#include <stdlib.h>
#include <stdio.h>
int main () {
srand48(123456 );
double x = drand48();
double y = drand48();
printf ("Ecco due numeri pseudocasuali: %lf %lf\n" , x, y);
return 0 ;
}
$ ./es_drand48
Ecco due numeri pseudocasuali: 0.940647 0.670256
$ ./es_drand48
Ecco due numeri pseudocasuali: 0.940647 0.670256
Stesso seme? Stessa sequenza!
Come generare un seed sempre diverso
Si può usare la funzione time(NULL)
, che restituisce il numero di secondi passati dalla mezzanotte del 01/01/1970
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main () {
srand48(time(NULL ));
double x = drand48();
double y = drand48();
printf ("Ecco due numeri pseudocasuali: %lf %lf\n" , x, y);
return 0 ;
}
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main () {
srand48(time(NULL ));
double x = drand48();
double y = drand48();
printf ("Ecco due numeri pseudocasuali: %lf %lf\n" , x, y);
return 0 ;
}
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
int main () {
srand48(time(NULL ));
double x = drand48();
double y = drand48();
printf ("Ecco due numeri pseudocasuali: %lf %lf\n" , x, y);
return 0 ;
}
$ ./es_drand48_2
Ecco due numeri pseudocasuali: 0.653414 0.670506
$ ./es_drand48_2
Ecco due numeri pseudocasuali: 0.524217 0.375096
Data la sua definizione, time
restituisce valori diversi solo se chiamata a più di un secondo di distanza
Ottenere numeri pseudocasuali in un intervallo
Vogliamo che i numeri siano distribuiti nell’intervallo [min, max)
Se servono interi possiamo usare due metodi equivalenti
Ricordando che drand48()
restituisce un double
∈ [ 0 , 1 )
Ricordando che lrand48()
restituisce un long int
∈ [ 0 , 2 31 )
Se servono double
è più comodo usare drand48()
int d_x = drand48() * (max - min) + min;
int l_x = lrand48() % (max - min) + min;
double d_x = drand48() * (max - min) + min;
double l_x = (lrand48() / (double ) RAND_MAX) * (max - min) + min;
int d_x = drand48() * (max - min) + min;
int l_x = lrand48() % (max - min) + min;
double d_x = drand48() * (max - min) + min;
double l_x = (lrand48() / (double ) RAND_MAX) * (max - min) + min;
RAND_MAX
è una costante simbolica (macro) definita in stdlib.h
Esempio di generazione di numeri in un intervallo
X % Y
dà come risultato un numero intero tra 0
e Y - 1
Aggiungiamo min
per ottenere un numero tra min
e max = min + Y - 1
#include <stdio.h>
#include <stdlib.h>
int main () {
srand48(598232 );
int i, r1;
double r2;
for (i = 0 ; i < 10 ; i++) {
r1 = lrand48() % 100 + 50 ;
r2 = 2. * drand48() - 1. ;
printf ("%d %lf\n" , r1, r2);
}
return 0 ;
}
#include <stdio.h>
#include <stdlib.h>
int main () {
srand48(598232 );
int i, r1;
double r2;
for (i = 0 ; i < 10 ; i++) {
r1 = lrand48() % 100 + 50 ;
r2 = 2. * drand48() - 1. ;
printf ("%d %lf\n" , r1, r2);
}
return 0 ;
}
$ ./es_drand48_intervallo
103 -0.374985
61 -0.376888
93 0.094238
63 0.892177
113 0.250517
82 -0.576272
61 0.141966
111 0.478965
131 0.186313
108 0.434002
Come funzionano drand48
/ lrand48
?
La sequenza generata è composta da interi
Il valore ( n + 1 ) -esimo è calcolato a partire dall’n -esimo tramite questa relazione:
X n + 1 = ( a X n + c ) % m
m , c e a sono costanti
X 0 = seed
, cioè il primo elemento della sequenza è il seed
Nel caso di drand48
, l’output della funzione è X n + 1 / RAND_MAX
Questo tipo di algoritmo è detto algoritmo lineare congruenziale
Se X n = X k con k < n , X n + 1 = X k + 1 : la sequenza si ripete!
Dettagli dell’implementazione
I valori di default delle costanti usate dalla libreria standard del C sono
m = 2 48 (valori grandi minimizzano la probabilità di ripetere la sequenza)
c = 0xB= 11
a = 0x5DEECE66D= 25214903917
La funzione rand()
usa m = 2 31 e quindi genera sequenze che si ripetono più spesso: meglio non usarla
Esistono altri tipi di generatori di numeri pseudocasuali più complessi e con proprietà migliori, ma drand48
va benissimo per ciò che faremo noi
Array, un primo algoritmo utile: il sorting Ordinare sequenze in base a un criterio è di fondamentale importanza per tantissime applicazioni Esistono tantissimi algoritmi di sorting , da usare a seconda delle diverse esigenze Qui un video che ne mostra schematicamente nove: