DidaWiki

Questa pagina è in sola lettura. Puoi visualizzare il sorgente, ma non puoi modificarlo. Contatta l'amministratore se pensi che ci sia un errore.
====== Esercitazione: Ordinamento ======

===== Esercizio 1: Ordinare una array di valori binari (0/1) =====
Implementare una funzione ''ordinaBin'' che ordina un array di valori binari (0/1) mettendo prima tutti i valori uguali a 0 e poi tutti qulli uguali ad 1. E' possibile realizzare la funzione ispezionando ogni elemento dell'array una sola volta. Come ? 

===== Esercizio 2: Selection sort, Merge Sort, quicksort =====
Scrivere tre funzioni che implementano gli algoritmi di ordinamento visti a lezione su array di double. 

Valutare i tempi di esecuzione su array di double lunghezza crescente generati casualmente nell'intervallo [0,1](usare il comando ''time''). Ci sono delle variazioni ?

Cercare una formula (approssimata) che fornisca il numero di istruzioni eseguite dai tre algoritmi di ordinamento  in funzione di //n//, lunghezza dell'array da ordinare.

===== Esercizio 3: (avanzato) Usare il ''qsort()'' della libreria standard C =====
La libreria standard C mette a disposizione una implementazione dell'algoritmo quicksort "generica" ovvero che può essere utilizzata con array di elementi di uno qualsiasi dei tipi base C. La funzione ha il seguente prototipo:
<code>
void qsort (void* buf, size_t num, size_t size, int (*compare) (const void*, const void*))
</code>
dove ''buf'' è il puntatore al primo elemento dell'array da ordinare, ''num''  è il numero di elementi dell'array, ''size'' è la lunghezza in byte di ogni elemento e ''compare'' è un puntatore a (nome di) una funzione che fa il confronto fra due elementi dell'array, ovvero l'indirizzo della prima istruzione della funzione (area text).
Una funzione ''compare'' utilizzabile a questo scopo deve avere tipo:
<code>
int compare (const void * x, const void * y); 
</code>
e deve confrontare ''*x'' e ''*y'' in modo da restituire un valore 
  * negativo -> se *x < *y
  * 0 -> se *x == *y
  * positivo -> se *x > *y
La parola chiave ''const'' significa che la funzione al suo interno non deve modificare mai le variabili puntate da x ed y. Inoltre è necessario inserire dei casti all'interno della funzione per specificare il tipo del puntatore prima di poterlo dereferenziare.
 
Ad esempio se sto lavorando con valori interi posso definire la funzione di confronto come:
<code>
int confronta_int (const void* x, const void* y) {
   int a = * (int *) x;
   int b = * (int *) y;
   return a-b;
}

#define N 6
int main(void){
int values[N] = {10, 21, 1 , 7 , 24 , 9};
qsort(values, N, sizeof(int), confronta_int);
.....
</code>
oppure per le stringhe
<code>
int confronta_string (const void* x, const void* y) {
   char* a = * (char* *) x;
   char* b = * (char* *) y;
   return strcmp(a,b);
}

#define N 10
int main(void){
int i;

char ** values = malloc(N*sizeof(char *));

for(i=0; i < n; i++) {
   values[i] = malloc((N+1)*sizeof(char));
   scanf(“%s”, values[i]);
}

qsort(values, N, sizeof(char *), confronta_string);
...
</code>

Utilizzare il ''qsort()'' della libreria standard per ordinare un array di interi, uno di double, uno di caratteri ed uno di strighe lunghe al massimo 40 caratteri.

Confrontare i tempi ottenti con quelli ottenuti le funzioni implementate nell'esercizio 2.