Esercizio 1

Obiettivo dell'esercizio

Realizzare ricerca binaria, bubble sort e insertion sort (descritti sotto) per vettore di interi. Punto di partenza: esercizio_1.c.

Scadenza: 10-05-2004

Introduzione all'ambiente DevCPP:

Ricerca Binaria

Scrivere una funzione
int ricerca(int v[], int n, int x)
che cerchi in un vettore ordinato di interi v[0]...v[n-1] un intero specificato x, e restituisca

La ricerca binaria si basa sul seguente metodo:
  1. Calcolare l'indice dell'elemento mediano v[n/2];
  2. Se v[n/2]==x, il numero e` stato trovato;
  3. Altrimenti

Bubble sort

Scrivere una funzione
int bubble_sort(int v[], int n)
che ordini un vettore di interi v[0],...,v[n-1] in senso crescente utilizzando il metodo del bubble sort, e che ritorni il numero di scambi effettuati durante l'ordinamento.
Il metodo del bubble-sort lavora in "passate" successive (k=1,...,n-1); alla passata k si applica la sequenza di scambi
Per i=n-1...k:    se v[i]<v[i-1], scambia i due elementi nel vettore.

Si dimostra facilmente che alla conclusione della passata k-esima il k-esimo elemento piu` piccolo e` salito alla posizione k-1.
Esempio: passata k=1

Posizione
 v
v
v
v
v
0
 5
5
5
5
2
1
 4
4
4
2
5
2
 2
 ==>
 2
 ==>
 2
 ==>
 4
 ==>
 4
3
 7
6
6
6
6
4
 6
7
7
7
7


i=4
i=3
i=2
i=1

Insertion sort

Scrivere una funzione
void insertion_sort(int v[], int n)
che ordini un vettore di interi v[0],...,v[n-1] in senso crescente utilizzando il metodo dell'insertion sort.
Il metodo dell'insertion sort lavora per iterazioni successive; all'iterazione k, gli elementi 0,...,k-1 del vettore sono gia` stati organizzati in un sotto-vettore ordinato. A questo punto il sotto-vettore viene esteso, e l'elemento v[k] viene inserito nella posizione corretta.
Esempio:

Posizione
 v
v
v
v
v
0
 5
4
2
2
2
1
 4
5
4
4
4
2
 2
 ==>
 2
 ==>
 5
 ==>
 5
 ==>
 5
3
 7
7
7
7
6
4
 6
6
6
6
7


k=1
k=2
k=3
k=4